algorithm - posibles - php combinaciones sin repeticion

Encuentra todas las combinaciones posibles de una representación de cadena de un número

Question

Dado un mapeo:

A: 1
B: 2
C: 3
...
...
...
Z: 26

Encuentra todas las formas posibles en que se puede representar un número. Por ejemplo, para una entrada: "121", podemos representarlo como:

ABA [using: 1 2 1]
LA [using: 12 1]
AU [using: 1 21]

Intenté pensar en usar algún tipo de enfoque de programación dinámica, pero no estoy seguro de cómo proceder. Me hicieron esta pregunta en una entrevista técnica.

Aquí hay una solución que podría pensar, por favor avíseme si esto se ve bien:

A[i]: Total number of ways to represent the sub-array number[0..i-1] using the integer to alphabet mapping.

Solución [¿Me estoy perdiendo algo?]:

A[0] = 1 // there is only 1 way to represent the subarray consisting of only 1 number
for(i = 1:A.size):
A[i] = A[i-1]
if(input[i-1]*10 + input[i] < 26):
A[i] += 1
end
end
print A[A.size-1]

Answer 1

Creo que el recorrido recursivo a través de todas las combinaciones posibles funcionaría bien:

mapping = {"1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G",
"8":"H", "9":"I", "10":"J",
"11":"K", "12":"L", "13":"M", "14":"N", "15":"O", "16":"P",
"17":"Q", "18":"R", "19":"S", "20":"T", "21":"U", "22":"V", "23":"W",
"24":"A", "25":"Y", "26":"Z"}
def represent(A, B):
if A == B == '''':
return [""]
ret = []
if A in mapping:
ret += [mapping[A] + r for r in represent(B, '''')]
if len(A) > 1:
ret += represent(A[:-1], A[-1]+B)
return ret
print represent("121", "")

Answer 2

En primer lugar, debemos encontrar una forma intuitiva de enumerar todas las posibilidades. Mi construcción simple, se da a continuación.

 let us assume a simple way to represent your integer in string format.
a1 a2 a3 a4 ....an, for instance in 121 a1 -> 1 a2 -> 2, a3 -> 1

Ahora,

Necesitamos averiguar el número de posibilidades de colocar un signo + entre dos caracteres. + significa la concatenación de caracteres aquí.

a1 - a2 - a3 - .... - an, - shows the places where ''+'' can be placed. So, number of positions is n - 1, where n is the string length.

Suponer que una posición puede o no tener un símbolo + se representará como un bit. Entonces, esto se reduce a cuántas cadenas de bits diferentes son posibles con la longitud de n-1, que es claramente 2 ^ (n-1). Ahora, para enumerar las posibilidades, recorra cada cadena y coloque los signos de la derecha + en las posiciones respectivas para obtener cada representación.

Para su ejemplo, 121

 Four bit strings are possible 00 01 10 11
1 2 1
1 2 + 1
1 + 2 1
1 + 2 + 1
And if you see a character followed by a +, just add the next char with the current one and do it sequentially to get the representation,
x + y z a + b + c d
would be (x+y) z (a+b+c) d

Espero eso ayude.

Y deberás ocuparte de los casos extremos donde el tamaño de algún entero sea> 26, por supuesto.

Answer 3

Para obtener el conteo, el enfoque de programación dinámica es bastante directo:

A[0] = 1
for i = 1:n
A[i] = 0
if input[i-1] > 0 // avoid 0
A[i] += A[i-1];
if i > 1 && // avoid index-out-of-bounds on i = 1
10 <= (10*input[i-2] + input[i-1]) <= 26 // check that number is 10-26
A[i] += A[i-2];

Si en su lugar desea enumerar todas las representaciones, la programación dinámica no es especialmente adecuada para esto, es mejor con un algoritmo recursivo simple.

Answer 4

Solo nosotros, la búsqueda de amplitud.

por ejemplo 121

Comience desde el primer entero, considere 1 carácter entero primero, mapa 1 a a, deje 21 luego 2 mapa de caracteres enteros 12 a L deje 1.

Answer 5

Suponiendo que solo necesita contar el número de combinaciones.

Suponiendo que 0 seguido de un entero en [1,9] no es una concatenación válida, entonces una estrategia de fuerza bruta sería:

Count(s,n)
x=0
if (s[n-1] is valid)
x=Count(s,n-1)
y=0
if (s[n-2] concat s[n-1] is valid)
y=Count(s,n-2)
return x+y

Una mejor estrategia sería usar divide y vencerás:

Count(s,start,n)
if (len is even)
{
//split s into equal left and right part, total count is left count multiply right count
x=Count(s,start,n/2) + Count(s,start+n/2,n/2);
y=0;
if (s[start+len/2-1] concat s[start+len/2] is valid)
{
//if middle two charaters concatenation is valid
//count left of the middle two characters
//count right of the middle two characters
//multiply the two counts and add to existing count
y=Count(s,start,len/2-1)*Count(s,start+len/2+1,len/2-1);
}
return x+y;
}
else
{
//there are three cases here:
//case 1: if middle character is valid,
//then count everything to the left of the middle character,
//count everything to the right of the middle character,
//multiply the two, assign to x
x=...
//case 2: if middle character concatenates the one to the left is valid,
//then count everything to the left of these two characters
//count everything to the right of these two characters
//multiply the two, assign to y
y=...
//case 3: if middle character concatenates the one to the right is valid,
//then count everything to the left of these two characters
//count everything to the right of these two characters
//multiply the two, assign to z
z=...
return x+y+z;
}

La solución de fuerza bruta tiene una complejidad temporal de T(n)=T(n-1)+T(n-2)+O(1) que es exponencial.

La solución de dividir y vencer tiene una complejidad temporal de T(n)=3T(n/2)+O(1) que es O (n ** lg3).

Espero que esto sea correcto.

Answer 6

¿Algo como esto?

Código Haskell:

import qualified Data.Map as M
import Data.Maybe (fromJust)
combs str = f str [] where
charMap = M.fromList $ zip (map show [1..]) [''A''..''Z'']
f [] result = [reverse result]
f (x:xs) result
| null xs =
case M.lookup [x] charMap of
Nothing -> ["The character " ++ [x] ++ " is not in the map."]
Just a -> [reverse $ a:result]
| otherwise =
case M.lookup [x,head xs] charMap of
Just a -> f (tail xs) (a:result)
++ (f xs ((fromJust $ M.lookup [x] charMap):result))
Nothing -> case M.lookup [x] charMap of
Nothing -> ["The character " ++ [x]
++ " is not in the map."]
Just a -> f xs (a:result)

Salida:

*Main> combs "121"
["LA","AU","ABA"]

Answer 7

Aquí está la solución basada en mi discusión aquí:

private static int decoder2(int[] input) {
int[] A = new int[input.length + 1];
A[0] = 1;
for(int i=1; i<input.length+1; i++) {
A[i] = 0;
if(input[i-1] > 0) {
A[i] += A[i-1];
}
if (i > 1 && (10*input[i-2] + input[i-1]) <= 26) {
A[i] += A[i-2];
}
System.out.println(A[i]);
}
return A[input.length];
}

Answer 8

Este problema se puede hacer en o (fib (n + 2)) tiempo con un algoritmo DP estándar. Tenemos exactamente n sub problemas y abotonamos podemos resolver cada problema con el tamaño i en o (fib (i)) tiempo. Sumando la serie da fib (n + 2).

Si consideras cuidadosamente la pregunta, ves que es una serie de Fibonacci. Tomé un código Fibonacci estándar y lo cambié para adaptarlo a nuestras condiciones.

El espacio obviamente está ligado al tamaño de todas las soluciones o (fib (n)).

Considera este pseudo código:

Map<Integer, String> mapping = new HashMap<Integer, String>();
List<String > iterative_fib_sequence(string input) {
int length = input.length;
if (length <= 1)
{
if (length==0)
{
return "";
}
else//input is a-j
{
return mapping.get(input);
}
}
List<String> b = new List<String>();
List<String> a = new List<String>(mapping.get(input.substring(0,0));
List<String> c = new List<String>();
for (int i = 1; i < length; ++i)
{
int dig2Prefix = input.substring(i-1, i); //Get a letter with 2 digit (k-z)
if (mapping.contains(dig2Prefix))
{
String word2Prefix = mapping.get(dig2Prefix);
foreach (String s in b)
{
c.Add(s.append(word2Prefix));
}
}
int dig1Prefix = input.substring(i, i); //Get a letter with 1 digit (a-j)
String word1Prefix = mapping.get(dig1Prefix);
foreach (String s in a)
{
c.Add(s.append(word1Prefix));
}
b = a;
a = c;
c = new List<String>();
}
return a;
}