todas repeticion programa posibles permutaciones numeros listar letras las generar con combinaciones algoritmo php arrays algorithm combinations

programa - php combinaciones sin repeticion



Algoritmo para obtener todas las combinaciones de cadenas posibles desde la matriz hasta cierta longitud (12)

¿Cuál es el mejor algoritmo para obtener todas las combinaciones de cadenas posibles de una matriz dada con un valor de longitud mínimo y máximo?

Nota: Esto agrega complejidad ya que el valor es variable a diferencia de las preguntas a las que están vinculadas.

Por ejemplo:

$letters = array(''a'',''b'',''c'',''1'',''2'',''3''); $min_length = 1; $max_length = 4; a b c 1 2 3 . . . aaaa a123 b123 c123

Algoritmo para obtener todas las combinaciones de cadenas posibles desde la matriz hasta cierta longitud.

El algoritmo se basa en encontrar el conjunto potencia de los índices, que a su vez se basa en encontrar todas las combinations (sin repetición) de índices con el tamaño: 1, 2,..., n.

Como mis habilidades en su idioma de preferencia "tienden a cero" , aquí hay una implementación de C # que podría usarse como punto de referencia:

using System; namespace Combinatorics { class StringPowerSet { static string[] set = { "a", "b", "c" }; static int[] subSetIndexes; //------------------------------------------------------------- static void Main(string[] args) { PrintSet(set, "Initial set"); FindPowerSet(set.Length); } //------------------------------------------------------------- private static void FindPowerSet(int n) { // Super set - all sets with size: 0, 1, ..., n - 1 for (int k = 0; k <= n - 1; k++) { subSetIndexes = new int[k]; CombinationsNoRepetition(k, 0, n - 1); } } //------------------------------------------------------------- private static void CombinationsNoRepetition(int k, int iBegin, int iEnd) { if (k == 0) { PrintSubSet(); return; } for (int i = iBegin; i <= iEnd; i++) { subSetIndexes[k - 1] = i; ++iBegin; CombinationsNoRepetition(k - 1, iBegin, iEnd); } } } }

Aquí están las funciones de impresión de ayuda:

//------------------------------------------------------------- private static void PrintSubSet() { Console.Write("("); for (int i = subSetIndexes.Length - 1; i >= 0; i--) { Console.Write(set[subSetIndexes[i]]); if (i > 0) { Console.Write(" ,"); } } Console.WriteLine(")"); } //------------------------------------------------------------- private static void PrintSet(string[] arr, string label = "") { Console.WriteLine(label); Console.Write("("); for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i]); if (i < arr.Length - 1) { Console.Write(" ,"); } } Console.WriteLine(")"); }

Entrada:

{a, b, c}

Salida:

() (a) (b) (c) (a, b) (a, c) (b, c)

Las variables ky nen la llamada de función CombinationsNoRepetitiondeterminan la longitud del primer conjunto y los últimos conjuntos, es decir, hay sus valores mínimo y máximo .

Casi una conversión de base

Esta solución está motivada por la observación de que, si no fuera por la posibilidad de repetir el carácter en el índice 0 de la matriz en la posición de orden superior de una combinación válida, este problema simplemente sería una conversión de base de decimal a la nueva base de todos los enteros desde 0 hasta (base ^ longitud) -1. Asi que,

0 = a 1 = b ... 1294 = 3332 1295 = 3333

La dificultad es que esto pierde combinaciones con uno o más ''a'' iniciales, como:

aa ... a1 aa1 aaa1

Y estas son las únicas soluciones que faltan. Entonces, para cada combinación generada con longitud inferior a max_length, simplemente podría agregar ''a'' (o lo que sea que esté en las letras [0]) al frente de la cadena, y emitir esa cadena, repitiendo si es necesario. Entonces, si generas la cadena ''b'', obtendrás:

b ab aab aaab

Esto funciona, pero es insatisfactorio, primero porque parece una solución kludged. En segundo lugar, no genera las soluciones en orden lexicográfico, lo que puede o no ser un problema. Tercero, sería muy bueno si la función para generar las combinaciones fuera biyectiva, de modo que conociéramos la combinación única que resulta de un entero decimal dado y el índice único de cualquier combinación. Esto será crítico en un momento.

Imagina que no hay cero

Si el índice cero nos está dando problemas, ¿por qué no eliminarlo? Digamos que cambiamos la matriz a:

letras = {∅, ''a'', ''b'', ''c'', ''1'', ''2'', ''3''}

donde ∅ es un marcador de posición arbitrario que nunca se utilizará. Ahora intentaremos representar los enteros decimales de 1 a base ^ max_length en la nueva base (en este caso, todavía 6, no 7) sin usar el dígito cero. Representaremos los números del 1 al 1 de base como es normal (1, 2, 3, ...) pero cuando obtengamos el número igual al de la base, en lugar de representarlo como 10, lo representaremos como el dígito base (por ejemplo, 6 en lugar de 10 en base 6). El siguiente número, base + 1, sería 11, luego 12 hasta 16 (que es igual a 12 decimales) y luego hasta 21. Cada número

a n , a n-1 , ..., a 1 , a 0

en la nueva base es igual a

a n * b n + a n-1 * b n-1 + ... + a 1 * b 1 + a 0 * b 0

en decimal, donde b es la nueva base.

Como he llegado a aprender, esto se denomina apropiadamente una numeración biyectiva . Tomando un ejemplo, en la base 6 tendríamos:

Base 10 Base 6 1 1 2 2 ... 6 6 7 11 8 12 ... 11 15 12 16 13 21 ... 36 56

Desde el enlace de Wikipedia anterior, el primer "dígito" del número en la nueva base es:

a 0 = m - q 0 k

donde k es la nueva base, m es el entero a convertir y q 0 = techo (m / k) -1. Tenga en cuenta la similitud con una conversión de base normal, donde la única diferencia es que q 0 sería suelo (m / k) o división entera ordinaria. Los "dígitos" subsiguientes se calculan de manera similar, utilizando q 0 en lugar de m para encontrar un 1 , etc.

Esta fórmula se puede dividir en dos casos:

  • (m mod k) == 0: a 0 = k y q 0 = (m div k) - 1
  • (m mod k)! = 0: a 0 = (m mod k) y q 0 = (m div k)

Este es el corazón del algoritmo. Para cualquier entero m podemos aplicar iterativamente esta fórmula hasta que q p == sea resultante 0. También tenga en cuenta que la conversión es, naturalmente, reversible. Dado un número 6666 en la base 6, el valor decimal es:

(6*6^3)+(6*6^2)+(6*6^1)+(6*6^0)=1554

Utilizamos este hecho para encontrar el rango de enteros a convertir para obtener todas las combinaciones de una cierta longitud. Lo siento, pero mis habilidades de PHP son inexistentes. Esperemos que el código de Java sea lo suficientemente claro. Dado:

char [] letters = new char [] {''0'',''a'',''b'',''c'',''1'',''2'',''3''}; int max_length = 4;

tenemos la función:

int b = letters.length - 1; // base to convert to int n = 0; for (int k = 0; k < max_length; k++) n = (n*b)+b; // number of combinations int remainder; for (int i = 1; i <= n; i++) { int current = i; // m and q_n in the formula String combination = ""; do { remainder = current % b; if (remainder == 0) { combination += letters[b]; current = current/b - 1; } else { combination += letters[remainder]; current = current/b; } } while (current > 0); System.out.println(combination); }

donde / representa división entera, o piso (a / b).

La función solo se basa en el entero de entrada y no en los resultados de los cálculos anteriores, por lo que las posibilidades de procesamiento en paralelo son bastante buenas.

Aquí está la salida con la entrada anterior. El dígito menos significativo es el primero, según su ejemplo.

a b c 1 2 3 aa ba ca 1a 2a 3a ab bb cb 1b 2b 3b ac bc cc 1c 2c 3c a1 b1 c1 11 21 31 a2 b2 c2 12 22 32 a3 b3 c3 13 23 33 aaa baa caa 1aa 2aa 3aa aba bba cba 1ba 2ba 3ba aca bca cca 1ca 2ca 3ca a1a b1a c1a 11a 21a 31a a2a b2a c2a 12a 22a 32a a3a b3a c3a 13a 23a 33a aab bab cab 1ab 2ab 3ab abb bbb cbb 1bb 2bb 3bb acb bcb ccb 1cb 2cb 3cb a1b b1b c1b 11b 21b 31b a2b b2b c2b 12b 22b 32b a3b b3b c3b 13b 23b 33b aac bac cac 1ac 2ac 3ac abc bbc cbc 1bc 2bc 3bc acc bcc ccc 1cc 2cc 3cc a1c b1c c1c 11c 21c 31c a2c b2c c2c 12c 22c 32c a3c b3c c3c 13c 23c 33c aa1 ba1 ca1 1a1 2a1 3a1 ab1 bb1 cb1 1b1 2b1 3b1 ac1 bc1 cc1 1c1 2c1 3c1 a11 b11 c11 111 211 311 a21 b21 c21 121 221 321 a31 b31 c31 131 231 331 aa2 ba2 ca2 1a2 2a2 3a2 ab2 bb2 cb2 1b2 2b2 3b2 ac2 bc2 cc2 1c2 2c2 3c2 a12 b12 c12 112 212 312 a22 b22 c22 122 222 322 a32 b32 c32 132 232 332 aa3 ba3 ca3 1a3 2a3 3a3 ab3 bb3 cb3 1b3 2b3 3b3 ac3 bc3 cc3 1c3 2c3 3c3 a13 b13 c13 113 213 313 a23 b23 c23 123 223 323 a33 b33 c33 133 233 333 aaaa baaa caaa 1aaa 2aaa 3aaa abaa bbaa cbaa 1baa 2baa 3baa acaa bcaa ccaa 1caa 2caa 3caa a1aa b1aa c1aa 11aa 21aa 31aa a2aa b2aa c2aa 12aa 22aa 32aa a3aa b3aa c3aa 13aa 23aa 33aa aaba baba caba 1aba 2aba 3aba abba bbba cbba 1bba 2bba 3bba acba bcba ccba 1cba 2cba 3cba a1ba b1ba c1ba 11ba 21ba 31ba a2ba b2ba c2ba 12ba 22ba 32ba a3ba b3ba c3ba 13ba 23ba 33ba aaca baca caca 1aca 2aca 3aca abca bbca cbca 1bca 2bca 3bca acca bcca ccca 1cca 2cca 3cca a1ca b1ca c1ca 11ca 21ca 31ca a2ca b2ca c2ca 12ca 22ca 32ca a3ca b3ca c3ca 13ca 23ca 33ca aa1a ba1a ca1a 1a1a 2a1a 3a1a ab1a bb1a cb1a 1b1a 2b1a 3b1a ac1a bc1a cc1a 1c1a 2c1a 3c1a a11a b11a c11a 111a 211a 311a a21a b21a c21a 121a 221a 321a a31a b31a c31a 131a 231a 331a aa2a ba2a ca2a 1a2a 2a2a 3a2a ab2a bb2a cb2a 1b2a 2b2a 3b2a ac2a bc2a cc2a 1c2a 2c2a 3c2a a12a b12a c12a 112a 212a 312a a22a b22a c22a 122a 222a 322a a32a b32a c32a 132a 232a 332a aa3a ba3a ca3a 1a3a 2a3a 3a3a ab3a bb3a cb3a 1b3a 2b3a 3b3a ac3a bc3a cc3a 1c3a 2c3a 3c3a a13a b13a c13a 113a 213a 313a a23a b23a c23a 123a 223a 323a a33a b33a c33a 133a 233a 333a aaab baab caab 1aab 2aab 3aab abab bbab cbab 1bab 2bab 3bab acab bcab ccab 1cab 2cab 3cab a1ab b1ab c1ab 11ab 21ab 31ab a2ab b2ab c2ab 12ab 22ab 32ab a3ab b3ab c3ab 13ab 23ab 33ab aabb babb cabb 1abb 2abb 3abb abbb bbbb cbbb 1bbb 2bbb 3bbb acbb bcbb ccbb 1cbb 2cbb 3cbb a1bb b1bb c1bb 11bb 21bb 31bb a2bb b2bb c2bb 12bb 22bb 32bb a3bb b3bb c3bb 13bb 23bb 33bb aacb bacb cacb 1acb 2acb 3acb abcb bbcb cbcb 1bcb 2bcb 3bcb accb bccb cccb 1ccb 2ccb 3ccb a1cb b1cb c1cb 11cb 21cb 31cb a2cb b2cb c2cb 12cb 22cb 32cb a3cb b3cb c3cb 13cb 23cb 33cb aa1b ba1b ca1b 1a1b 2a1b 3a1b ab1b bb1b cb1b 1b1b 2b1b 3b1b ac1b bc1b cc1b 1c1b 2c1b 3c1b a11b b11b c11b 111b 211b 311b a21b b21b c21b 121b 221b 321b a31b b31b c31b 131b 231b 331b aa2b ba2b ca2b 1a2b 2a2b 3a2b ab2b bb2b cb2b 1b2b 2b2b 3b2b ac2b bc2b cc2b 1c2b 2c2b 3c2b a12b b12b c12b 112b 212b 312b a22b b22b c22b 122b 222b 322b a32b b32b c32b 132b 232b 332b aa3b ba3b ca3b 1a3b 2a3b 3a3b ab3b bb3b cb3b 1b3b 2b3b 3b3b ac3b bc3b cc3b 1c3b 2c3b 3c3b a13b b13b c13b 113b 213b 313b a23b b23b c23b 123b 223b 323b a33b b33b c33b 133b 233b 333b aaac baac caac 1aac 2aac 3aac abac bbac cbac 1bac 2bac 3bac acac bcac ccac 1cac 2cac 3cac a1ac b1ac c1ac 11ac 21ac 31ac a2ac b2ac c2ac 12ac 22ac 32ac a3ac b3ac c3ac 13ac 23ac 33ac aabc babc cabc 1abc 2abc 3abc abbc bbbc cbbc 1bbc 2bbc 3bbc acbc bcbc ccbc 1cbc 2cbc 3cbc a1bc b1bc c1bc 11bc 21bc 31bc a2bc b2bc c2bc 12bc 22bc 32bc a3bc b3bc c3bc 13bc 23bc 33bc aacc bacc cacc 1acc 2acc 3acc abcc bbcc cbcc 1bcc 2bcc 3bcc accc bccc cccc 1ccc 2ccc 3ccc a1cc b1cc c1cc 11cc 21cc 31cc a2cc b2cc c2cc 12cc 22cc 32cc a3cc b3cc c3cc 13cc 23cc 33cc aa1c ba1c ca1c 1a1c 2a1c 3a1c ab1c bb1c cb1c 1b1c 2b1c 3b1c ac1c bc1c cc1c 1c1c 2c1c 3c1c a11c b11c c11c 111c 211c 311c a21c b21c c21c 121c 221c 321c a31c b31c c31c 131c 231c 331c aa2c ba2c ca2c 1a2c 2a2c 3a2c ab2c bb2c cb2c 1b2c 2b2c 3b2c ac2c bc2c cc2c 1c2c 2c2c 3c2c a12c b12c c12c 112c 212c 312c a22c b22c c22c 122c 222c 322c a32c b32c c32c 132c 232c 332c aa3c ba3c ca3c 1a3c 2a3c 3a3c ab3c bb3c cb3c 1b3c 2b3c 3b3c ac3c bc3c cc3c 1c3c 2c3c 3c3c a13c b13c c13c 113c 213c 313c a23c b23c c23c 123c 223c 323c a33c b33c c33c 133c 233c 333c aaa1 baa1 caa1 1aa1 2aa1 3aa1 aba1 bba1 cba1 1ba1 2ba1 3ba1 aca1 bca1 cca1 1ca1 2ca1 3ca1 a1a1 b1a1 c1a1 11a1 21a1 31a1 a2a1 b2a1 c2a1 12a1 22a1 32a1 a3a1 b3a1 c3a1 13a1 23a1 33a1 aab1 bab1 cab1 1ab1 2ab1 3ab1 abb1 bbb1 cbb1 1bb1 2bb1 3bb1 acb1 bcb1 ccb1 1cb1 2cb1 3cb1 a1b1 b1b1 c1b1 11b1 21b1 31b1 a2b1 b2b1 c2b1 12b1 22b1 32b1 a3b1 b3b1 c3b1 13b1 23b1 33b1 aac1 bac1 cac1 1ac1 2ac1 3ac1 abc1 bbc1 cbc1 1bc1 2bc1 3bc1 acc1 bcc1 ccc1 1cc1 2cc1 3cc1 a1c1 b1c1 c1c1 11c1 21c1 31c1 a2c1 b2c1 c2c1 12c1 22c1 32c1 a3c1 b3c1 c3c1 13c1 23c1 33c1 aa11 ba11 ca11 1a11 2a11 3a11 ab11 bb11 cb11 1b11 2b11 3b11 ac11 bc11 cc11 1c11 2c11 3c11 a111 b111 c111 1111 2111 3111 a211 b211 c211 1211 2211 3211 a311 b311 c311 1311 2311 3311 aa21 ba21 ca21 1a21 2a21 3a21 ab21 bb21 cb21 1b21 2b21 3b21 ac21 bc21 cc21 1c21 2c21 3c21 a121 b121 c121 1121 2121 3121 a221 b221 c221 1221 2221 3221 a321 b321 c321 1321 2321 3321 aa31 ba31 ca31 1a31 2a31 3a31 ab31 bb31 cb31 1b31 2b31 3b31 ac31 bc31 cc31 1c31 2c31 3c31 a131 b131 c131 1131 2131 3131 a231 b231 c231 1231 2231 3231 a331 b331 c331 1331 2331 3331 aaa2 baa2 caa2 1aa2 2aa2 3aa2 aba2 bba2 cba2 1ba2 2ba2 3ba2 aca2 bca2 cca2 1ca2 2ca2 3ca2 a1a2 b1a2 c1a2 11a2 21a2 31a2 a2a2 b2a2 c2a2 12a2 22a2 32a2 a3a2 b3a2 c3a2 13a2 23a2 33a2 aab2 bab2 cab2 1ab2 2ab2 3ab2 abb2 bbb2 cbb2 1bb2 2bb2 3bb2 acb2 bcb2 ccb2 1cb2 2cb2 3cb2 a1b2 b1b2 c1b2 11b2 21b2 31b2 a2b2 b2b2 c2b2 12b2 22b2 32b2 a3b2 b3b2 c3b2 13b2 23b2 33b2 aac2 bac2 cac2 1ac2 2ac2 3ac2 abc2 bbc2 cbc2 1bc2 2bc2 3bc2 acc2 bcc2 ccc2 1cc2 2cc2 3cc2 a1c2 b1c2 c1c2 11c2 21c2 31c2 a2c2 b2c2 c2c2 12c2 22c2 32c2 a3c2 b3c2 c3c2 13c2 23c2 33c2 aa12 ba12 ca12 1a12 2a12 3a12 ab12 bb12 cb12 1b12 2b12 3b12 ac12 bc12 cc12 1c12 2c12 3c12 a112 b112 c112 1112 2112 3112 a212 b212 c212 1212 2212 3212 a312 b312 c312 1312 2312 3312 aa22 ba22 ca22 1a22 2a22 3a22 ab22 bb22 cb22 1b22 2b22 3b22 ac22 bc22 cc22 1c22 2c22 3c22 a122 b122 c122 1122 2122 3122 a222 b222 c222 1222 2222 3222 a322 b322 c322 1322 2322 3322 aa32 ba32 ca32 1a32 2a32 3a32 ab32 bb32 cb32 1b32 2b32 3b32 ac32 bc32 cc32 1c32 2c32 3c32 a132 b132 c132 1132 2132 3132 a232 b232 c232 1232 2232 3232 a332 b332 c332 1332 2332 3332 aaa3 baa3 caa3 1aa3 2aa3 3aa3 aba3 bba3 cba3 1ba3 2ba3 3ba3 aca3 bca3 cca3 1ca3 2ca3 3ca3 a1a3 b1a3 c1a3 11a3 21a3 31a3 a2a3 b2a3 c2a3 12a3 22a3 32a3 a3a3 b3a3 c3a3 13a3 23a3 33a3 aab3 bab3 cab3 1ab3 2ab3 3ab3 abb3 bbb3 cbb3 1bb3 2bb3 3bb3 acb3 bcb3 ccb3 1cb3 2cb3 3cb3 a1b3 b1b3 c1b3 11b3 21b3 31b3 a2b3 b2b3 c2b3 12b3 22b3 32b3 a3b3 b3b3 c3b3 13b3 23b3 33b3 aac3 bac3 cac3 1ac3 2ac3 3ac3 abc3 bbc3 cbc3 1bc3 2bc3 3bc3 acc3 bcc3 ccc3 1cc3 2cc3 3cc3 a1c3 b1c3 c1c3 11c3 21c3 31c3 a2c3 b2c3 c2c3 12c3 22c3 32c3 a3c3 b3c3 c3c3 13c3 23c3 33c3 aa13 ba13 ca13 1a13 2a13 3a13 ab13 bb13 cb13 1b13 2b13 3b13 ac13 bc13 cc13 1c13 2c13 3c13 a113 b113 c113 1113 2113 3113 a213 b213 c213 1213 2213 3213 a313 b313 c313 1313 2313 3313 aa23 ba23 ca23 1a23 2a23 3a23 ab23 bb23 cb23 1b23 2b23 3b23 ac23 bc23 cc23 1c23 2c23 3c23 a123 b123 c123 1123 2123 3123 a223 b223 c223 1223 2223 3223 a323 b323 c323 1323 2323 3323 aa33 ba33 ca33 1a33 2a33 3a33 ab33 bb33 cb33 1b33 2b33 3b33 ac33 bc33 cc33 1c33 2c33 3c33 a133 b133 c133 1133 2133 3133 a233 b233 c233 1233 2233 3233 a333 b333 c333 1333 2333 3333

Este es un idioma diferente, pero ¿son los resultados que está buscando al final?

>>> import itertools >>> def my_combinations(string, max_length): for repeat in range(1, max_length + 1): for result in itertools.product(string, repeat=repeat): yield ''''.join(result) >>> print(*my_combinations(''abc123'', 4), sep=''/n'') a b c 1 2 3 aa ab ac a1 a2 a3 ba bb bc b1 b2 b3 ca cb cc c1 c2 c3 1a 1b 1c 11 12 13 2a 2b 2c 21 22 23 3a 3b 3c 31 32 33 aaa aab aac aa1 aa2 aa3 aba abb abc ab1 ab2 ab3 aca acb acc ac1 ac2 ac3 a1a a1b a1c a11 a12 a13 a2a a2b a2c a21 a22 a23 a3a a3b a3c a31 a32 a33 baa bab bac ba1 ba2 ba3 bba bbb bbc bb1 bb2 bb3 bca bcb bcc bc1 bc2 bc3 b1a b1b b1c b11 b12 b13 b2a b2b b2c b21 b22 b23 b3a b3b b3c b31 b32 b33 caa cab cac ca1 ca2 ca3 cba cbb cbc cb1 cb2 cb3 cca ccb ccc cc1 cc2 cc3 c1a c1b c1c c11 c12 c13 c2a c2b c2c c21 c22 c23 c3a c3b c3c c31 c32 c33 1aa 1ab 1ac 1a1 1a2 1a3 1ba 1bb 1bc 1b1 1b2 1b3 1ca 1cb 1cc 1c1 1c2 1c3 11a 11b 11c 111 112 113 12a 12b 12c 121 122 123 13a 13b 13c 131 132 133 2aa 2ab 2ac 2a1 2a2 2a3 2ba 2bb 2bc 2b1 2b2 2b3 2ca 2cb 2cc 2c1 2c2 2c3 21a 21b 21c 211 212 213 22a 22b 22c 221 222 223 23a 23b 23c 231 232 233 3aa 3ab 3ac 3a1 3a2 3a3 3ba 3bb 3bc 3b1 3b2 3b3 3ca 3cb 3cc 3c1 3c2 3c3 31a 31b 31c 311 312 313 32a 32b 32c 321 322 323 33a 33b 33c 331 332 333 aaaa aaab aaac aaa1 aaa2 aaa3 aaba aabb aabc aab1 aab2 aab3 aaca aacb aacc aac1 aac2 aac3 aa1a aa1b aa1c aa11 aa12 aa13 aa2a aa2b aa2c aa21 aa22 aa23 aa3a aa3b aa3c aa31 aa32 aa33 abaa abab abac aba1 aba2 aba3 abba abbb abbc abb1 abb2 abb3 abca abcb abcc abc1 abc2 abc3 ab1a ab1b ab1c ab11 ab12 ab13 ab2a ab2b ab2c ab21 ab22 ab23 ab3a ab3b ab3c ab31 ab32 ab33 acaa acab acac aca1 aca2 aca3 acba acbb acbc acb1 acb2 acb3 acca accb accc acc1 acc2 acc3 ac1a ac1b ac1c ac11 ac12 ac13 ac2a ac2b ac2c ac21 ac22 ac23 ac3a ac3b ac3c ac31 ac32 ac33 a1aa a1ab a1ac a1a1 a1a2 a1a3 a1ba a1bb a1bc a1b1 a1b2 a1b3 a1ca a1cb a1cc a1c1 a1c2 a1c3 a11a a11b a11c a111 a112 a113 a12a a12b a12c a121 a122 a123 a13a a13b a13c a131 a132 a133 a2aa a2ab a2ac a2a1 a2a2 a2a3 a2ba a2bb a2bc a2b1 a2b2 a2b3 a2ca a2cb a2cc a2c1 a2c2 a2c3 a21a a21b a21c a211 a212 a213 a22a a22b a22c a221 a222 a223 a23a a23b a23c a231 a232 a233 a3aa a3ab a3ac a3a1 a3a2 a3a3 a3ba a3bb a3bc a3b1 a3b2 a3b3 a3ca a3cb a3cc a3c1 a3c2 a3c3 a31a a31b a31c a311 a312 a313 a32a a32b a32c a321 a322 a323 a33a a33b a33c a331 a332 a333 baaa baab baac baa1 baa2 baa3 baba babb babc bab1 bab2 bab3 baca bacb bacc bac1 bac2 bac3 ba1a ba1b ba1c ba11 ba12 ba13 ba2a ba2b ba2c ba21 ba22 ba23 ba3a ba3b ba3c ba31 ba32 ba33 bbaa bbab bbac bba1 bba2 bba3 bbba bbbb bbbc bbb1 bbb2 bbb3 bbca bbcb bbcc bbc1 bbc2 bbc3 bb1a bb1b bb1c bb11 bb12 bb13 bb2a bb2b bb2c bb21 bb22 bb23 bb3a bb3b bb3c bb31 bb32 bb33 bcaa bcab bcac bca1 bca2 bca3 bcba bcbb bcbc bcb1 bcb2 bcb3 bcca bccb bccc bcc1 bcc2 bcc3 bc1a bc1b bc1c bc11 bc12 bc13 bc2a bc2b bc2c bc21 bc22 bc23 bc3a bc3b bc3c bc31 bc32 bc33 b1aa b1ab b1ac b1a1 b1a2 b1a3 b1ba b1bb b1bc b1b1 b1b2 b1b3 b1ca b1cb b1cc b1c1 b1c2 b1c3 b11a b11b b11c b111 b112 b113 b12a b12b b12c b121 b122 b123 b13a b13b b13c b131 b132 b133 b2aa b2ab b2ac b2a1 b2a2 b2a3 b2ba b2bb b2bc b2b1 b2b2 b2b3 b2ca b2cb b2cc b2c1 b2c2 b2c3 b21a b21b b21c b211 b212 b213 b22a b22b b22c b221 b222 b223 b23a b23b b23c b231 b232 b233 b3aa b3ab b3ac b3a1 b3a2 b3a3 b3ba b3bb b3bc b3b1 b3b2 b3b3 b3ca b3cb b3cc b3c1 b3c2 b3c3 b31a b31b b31c b311 b312 b313 b32a b32b b32c b321 b322 b323 b33a b33b b33c b331 b332 b333 caaa caab caac caa1 caa2 caa3 caba cabb cabc cab1 cab2 cab3 caca cacb cacc cac1 cac2 cac3 ca1a ca1b ca1c ca11 ca12 ca13 ca2a ca2b ca2c ca21 ca22 ca23 ca3a ca3b ca3c ca31 ca32 ca33 cbaa cbab cbac cba1 cba2 cba3 cbba cbbb cbbc cbb1 cbb2 cbb3 cbca cbcb cbcc cbc1 cbc2 cbc3 cb1a cb1b cb1c cb11 cb12 cb13 cb2a cb2b cb2c cb21 cb22 cb23 cb3a cb3b cb3c cb31 cb32 cb33 ccaa ccab ccac cca1 cca2 cca3 ccba ccbb ccbc ccb1 ccb2 ccb3 ccca cccb cccc ccc1 ccc2 ccc3 cc1a cc1b cc1c cc11 cc12 cc13 cc2a cc2b cc2c cc21 cc22 cc23 cc3a cc3b cc3c cc31 cc32 cc33 c1aa c1ab c1ac c1a1 c1a2 c1a3 c1ba c1bb c1bc c1b1 c1b2 c1b3 c1ca c1cb c1cc c1c1 c1c2 c1c3 c11a c11b c11c c111 c112 c113 c12a c12b c12c c121 c122 c123 c13a c13b c13c c131 c132 c133 c2aa c2ab c2ac c2a1 c2a2 c2a3 c2ba c2bb c2bc c2b1 c2b2 c2b3 c2ca c2cb c2cc c2c1 c2c2 c2c3 c21a c21b c21c c211 c212 c213 c22a c22b c22c c221 c222 c223 c23a c23b c23c c231 c232 c233 c3aa c3ab c3ac c3a1 c3a2 c3a3 c3ba c3bb c3bc c3b1 c3b2 c3b3 c3ca c3cb c3cc c3c1 c3c2 c3c3 c31a c31b c31c c311 c312 c313 c32a c32b c32c c321 c322 c323 c33a c33b c33c c331 c332 c333 1aaa 1aab 1aac 1aa1 1aa2 1aa3 1aba 1abb 1abc 1ab1 1ab2 1ab3 1aca 1acb 1acc 1ac1 1ac2 1ac3 1a1a 1a1b 1a1c 1a11 1a12 1a13 1a2a 1a2b 1a2c 1a21 1a22 1a23 1a3a 1a3b 1a3c 1a31 1a32 1a33 1baa 1bab 1bac 1ba1 1ba2 1ba3 1bba 1bbb 1bbc 1bb1 1bb2 1bb3 1bca 1bcb 1bcc 1bc1 1bc2 1bc3 1b1a 1b1b 1b1c 1b11 1b12 1b13 1b2a 1b2b 1b2c 1b21 1b22 1b23 1b3a 1b3b 1b3c 1b31 1b32 1b33 1caa 1cab 1cac 1ca1 1ca2 1ca3 1cba 1cbb 1cbc 1cb1 1cb2 1cb3 1cca 1ccb 1ccc 1cc1 1cc2 1cc3 1c1a 1c1b 1c1c 1c11 1c12 1c13 1c2a 1c2b 1c2c 1c21 1c22 1c23 1c3a 1c3b 1c3c 1c31 1c32 1c33 11aa 11ab 11ac 11a1 11a2 11a3 11ba 11bb 11bc 11b1 11b2 11b3 11ca 11cb 11cc 11c1 11c2 11c3 111a 111b 111c 1111 1112 1113 112a 112b 112c 1121 1122 1123 113a 113b 113c 1131 1132 1133 12aa 12ab 12ac 12a1 12a2 12a3 12ba 12bb 12bc 12b1 12b2 12b3 12ca 12cb 12cc 12c1 12c2 12c3 121a 121b 121c 1211 1212 1213 122a 122b 122c 1221 1222 1223 123a 123b 123c 1231 1232 1233 13aa 13ab 13ac 13a1 13a2 13a3 13ba 13bb 13bc 13b1 13b2 13b3 13ca 13cb 13cc 13c1 13c2 13c3 131a 131b 131c 1311 1312 1313 132a 132b 132c 1321 1322 1323 133a 133b 133c 1331 1332 1333 2aaa 2aab 2aac 2aa1 2aa2 2aa3 2aba 2abb 2abc 2ab1 2ab2 2ab3 2aca 2acb 2acc 2ac1 2ac2 2ac3 2a1a 2a1b 2a1c 2a11 2a12 2a13 2a2a 2a2b 2a2c 2a21 2a22 2a23 2a3a 2a3b 2a3c 2a31 2a32 2a33 2baa 2bab 2bac 2ba1 2ba2 2ba3 2bba 2bbb 2bbc 2bb1 2bb2 2bb3 2bca 2bcb 2bcc 2bc1 2bc2 2bc3 2b1a 2b1b 2b1c 2b11 2b12 2b13 2b2a 2b2b 2b2c 2b21 2b22 2b23 2b3a 2b3b 2b3c 2b31 2b32 2b33 2caa 2cab 2cac 2ca1 2ca2 2ca3 2cba 2cbb 2cbc 2cb1 2cb2 2cb3 2cca 2ccb 2ccc 2cc1 2cc2 2cc3 2c1a 2c1b 2c1c 2c11 2c12 2c13 2c2a 2c2b 2c2c 2c21 2c22 2c23 2c3a 2c3b 2c3c 2c31 2c32 2c33 21aa 21ab 21ac 21a1 21a2 21a3 21ba 21bb 21bc 21b1 21b2 21b3 21ca 21cb 21cc 21c1 21c2 21c3 211a 211b 211c 2111 2112 2113 212a 212b 212c 2121 2122 2123 213a 213b 213c 2131 2132 2133 22aa 22ab 22ac 22a1 22a2 22a3 22ba 22bb 22bc 22b1 22b2 22b3 22ca 22cb 22cc 22c1 22c2 22c3 221a 221b 221c 2211 2212 2213 222a 222b 222c 2221 2222 2223 223a 223b 223c 2231 2232 2233 23aa 23ab 23ac 23a1 23a2 23a3 23ba 23bb 23bc 23b1 23b2 23b3 23ca 23cb 23cc 23c1 23c2 23c3 231a 231b 231c 2311 2312 2313 232a 232b 232c 2321 2322 2323 233a 233b 233c 2331 2332 2333 3aaa 3aab 3aac 3aa1 3aa2 3aa3 3aba 3abb 3abc 3ab1 3ab2 3ab3 3aca 3acb 3acc 3ac1 3ac2 3ac3 3a1a 3a1b 3a1c 3a11 3a12 3a13 3a2a 3a2b 3a2c 3a21 3a22 3a23 3a3a 3a3b 3a3c 3a31 3a32 3a33 3baa 3bab 3bac 3ba1 3ba2 3ba3 3bba 3bbb 3bbc 3bb1 3bb2 3bb3 3bca 3bcb 3bcc 3bc1 3bc2 3bc3 3b1a 3b1b 3b1c 3b11 3b12 3b13 3b2a 3b2b 3b2c 3b21 3b22 3b23 3b3a 3b3b 3b3c 3b31 3b32 3b33 3caa 3cab 3cac 3ca1 3ca2 3ca3 3cba 3cbb 3cbc 3cb1 3cb2 3cb3 3cca 3ccb 3ccc 3cc1 3cc2 3cc3 3c1a 3c1b 3c1c 3c11 3c12 3c13 3c2a 3c2b 3c2c 3c21 3c22 3c23 3c3a 3c3b 3c3c 3c31 3c32 3c33 31aa 31ab 31ac 31a1 31a2 31a3 31ba 31bb 31bc 31b1 31b2 31b3 31ca 31cb 31cc 31c1 31c2 31c3 311a 311b 311c 3111 3112 3113 312a 312b 312c 3121 3122 3123 313a 313b 313c 3131 3132 3133 32aa 32ab 32ac 32a1 32a2 32a3 32ba 32bb 32bc 32b1 32b2 32b3 32ca 32cb 32cc 32c1 32c2 32c3 321a 321b 321c 3211 3212 3213 322a 322b 322c 3221 3222 3223 323a 323b 323c 3231 3232 3233 33aa 33ab 33ac 33a1 33a2 33a3 33ba 33bb 33bc 33b1 33b2 33b3 33ca 33cb 33cc 33c1 33c2 33c3 331a 331b 331c 3311 3312 3313 332a 332b 332c 3321 3322 3323 333a 333b 333c 3331 3332 3333 >>>

La mejor manera de resolver este problema es utilizar una solución recursiva, espero que los comentarios en línea sean lo suficientemente buenos para entender la solución:

<?php // Recursive method that print all permutation of a given length // @param $arr input array // @param $arrLen just the length of the above array // @param $size length or size for which we are making all permutation // @param $perArr this is a temporary array to hold the current permutation being created // @param $pos current position of $perArr function printPermutation($arr, $arrLen, $size, $perArr, $pos) { if ($size==$pos) { //if $pos reach $size then we have found one permutation for ($i=0; $i<$size; $i++) print $perArr[$i]; print ("/n"); return; } for ($i=0; $i<$arrLen; $i++) { $perArr[$pos] = $arr[$i]; //put i''th char in current position //The recursive call that move to next position with $pos+1 printPermutation($arr, $arrLen, $size, $perArr, $pos+1); } } //all printPermutation method with 1 - maxLen function showAllPermutation($letters, $maxLen) { $length = count($letters); $perArr = array(); for ($i=1; $i<=$maxLen; $i++) { printPermutation ($letters, $length, $i, $perArr, 0); } } //main $letters = array(''a'',''b'',''c'',''1'',''2'',''3''); $max_length = 4; showAllPermutation ($letters, $max_length); ?>

Si está interesado, aquí está la salida muy grande del código anterior: stdout:

a b c 1 2 3 aa ab ac a1 a2 a3 ba bb bc b1 b2 b3 ca cb cc c1 c2 c3 1a 1b 1c 11 12 13 2a 2b 2c 21 22 23 3a 3b 3c 31 32 33 aaa aab aac aa1 aa2 aa3 aba abb abc ab1 ab2 ab3 aca acb acc ac1 ac2 ac3 a1a a1b a1c a11 a12 a13 a2a a2b a2c a21 a22 a23 a3a a3b a3c a31 a32 a33 baa bab bac ba1 ba2 ba3 bba bbb bbc bb1 bb2 bb3 bca bcb bcc bc1 bc2 bc3 b1a b1b b1c b11 b12 b13 b2a b2b b2c b21 b22 b23 b3a b3b b3c b31 b32 b33 caa cab cac ca1 ca2 ca3 cba cbb cbc cb1 cb2 cb3 cca ccb ccc cc1 cc2 cc3 c1a c1b c1c c11 c12 c13 c2a c2b c2c c21 c22 c23 c3a c3b c3c c31 c32 c33 1aa 1ab 1ac 1a1 1a2 1a3 1ba 1bb 1bc 1b1 1b2 1b3 1ca 1cb 1cc 1c1 1c2 1c3 11a 11b 11c 111 112 113 12a 12b 12c 121 122 123 13a 13b 13c 131 132 133 2aa 2ab 2ac 2a1 2a2 2a3 2ba 2bb 2bc 2b1 2b2 2b3 2ca 2cb 2cc 2c1 2c2 2c3 21a 21b 21c 211 212 213 22a 22b 22c 221 222 223 23a 23b 23c 231 232 233 3aa 3ab 3ac 3a1 3a2 3a3 3ba 3bb 3bc 3b1 3b2 3b3 3ca 3cb 3cc 3c1 3c2 3c3 31a 31b 31c 311 312 313 32a 32b 32c 321 322 323 33a 33b 33c 331 332 333 aaaa aaab aaac aaa1 aaa2 aaa3 aaba aabb aabc aab1 aab2 aab3 aaca aacb aacc aac1 aac2 aac3 aa1a aa1b aa1c aa11 aa12 aa13 aa2a aa2b aa2c aa21 aa22 aa23 aa3a aa3b aa3c aa31 aa32 aa33 abaa abab abac aba1 aba2 aba3 abba abbb abbc abb1 abb2 abb3 abca abcb abcc abc1 abc2 abc3 ab1a ab1b ab1c ab11 ab12 ab13 ab2a ab2b ab2c ab21 ab22 ab23 ab3a ab3b ab3c ab31 ab32 ab33 acaa acab acac aca1 aca2 aca3 acba acbb acbc acb1 acb2 acb3 acca accb accc acc1 acc2 acc3 ac1a ac1b ac1c ac11 ac12 ac13 ac2a ac2b ac2c ac21 ac22 ac23 ac3a ac3b ac3c ac31 ac32 ac33 a1aa a1ab a1ac a1a1 a1a2 a1a3 a1ba a1bb a1bc a1b1 a1b2 a1b3 a1ca a1cb a1cc a1c1 a1c2 a1c3 a11a a11b a11c a111 a112 a113 a12a a12b a12c a121 a122 a123 a13a a13b a13c a131 a132 a133 a2aa a2ab a2ac a2a1 a2a2 a2a3 a2ba a2bb a2bc a2b1 a2b2 a2b3 a2ca a2cb a2cc a2c1 a2c2 a2c3 a21a a21b a21c a211 a212 a213 a22a a22b a22c a221 a222 a223 a23a a23b a23c a231 a232 a233 a3aa a3ab a3ac a3a1 a3a2 a3a3 a3ba a3bb a3bc a3b1 a3b2 a3b3 a3ca a3cb a3cc a3c1 a3c2 a3c3 a31a a31b a31c a311 a312 a313 a32a a32b a32c a321 a322 a323 a33a a33b a33c a331 a332 a333 baaa baab baac baa1 baa2 baa3 baba babb babc bab1 bab2 bab3 baca bacb bacc bac1 bac2 bac3 ba1a ba1b ba1c ba11 ba12 ba13 ba2a ba2b ba2c ba21 ba22 ba23 ba3a ba3b ba3c ba31 ba32 ba33 bbaa bbab bbac bba1 bba2 bba3 bbba bbbb bbbc bbb1 bbb2 bbb3 bbca bbcb bbcc bbc1 bbc2 bbc3 bb1a bb1b bb1c bb11 bb12 bb13 bb2a bb2b bb2c bb21 bb22 bb23 bb3a bb3b bb3c bb31 bb32 bb33 bcaa bcab bcac bca1 bca2 bca3 bcba bcbb bcbc bcb1 bcb2 bcb3 bcca bccb bccc bcc1 bcc2 bcc3 bc1a bc1b bc1c bc11 bc12 bc13 bc2a bc2b bc2c bc21 bc22 bc23 bc3a bc3b bc3c bc31 bc32 bc33 b1aa b1ab b1ac b1a1 b1a2 b1a3 b1ba b1bb b1bc b1b1 b1b2 b1b3 b1ca b1cb b1cc b1c1 b1c2 b1c3 b11a b11b b11c b111 b112 b113 b12a b12b b12c b121 b122 b123 b13a b13b b13c b131 b132 b133 b2aa b2ab b2ac b2a1 b2a2 b2a3 b2ba b2bb b2bc b2b1 b2b2 b2b3 b2ca b2cb b2cc b2c1 b2c2 b2c3 b21a b21b b21c b211 b212 b213 b22a b22b b22c b221 b222 b223 b23a b23b b23c b231 b232 b233 b3aa b3ab b3ac b3a1 b3a2 b3a3 b3ba b3bb b3bc b3b1 b3b2 b3b3 b3ca b3cb b3cc b3c1 b3c2 b3c3 b31a b31b b31c b311 b312 b313 b32a b32b b32c b321 b322 b323 b33a b33b b33c b331 b332 b333 caaa caab caac caa1 caa2 caa3 caba cabb cabc cab1 cab2 cab3 caca cacb cacc cac1 cac2 cac3 ca1a ca1b ca1c ca11 ca12 ca13 ca2a ca2b ca2c ca21 ca22 ca23 ca3a ca3b ca3c ca31 ca32 ca33 cbaa cbab cbac cba1 cba2 cba3 cbba cbbb cbbc cbb1 cbb2 cbb3 cbca cbcb cbcc cbc1 cbc2 cbc3 cb1a cb1b cb1c cb11 cb12 cb13 cb2a cb2b cb2c cb21 cb22 cb23 cb3a cb3b cb3c cb31 cb32 cb33 ccaa ccab ccac cca1 cca2 cca3 ccba ccbb ccbc ccb1 ccb2 ccb3 ccca cccb cccc ccc1 ccc2 ccc3 cc1a cc1b cc1c cc11 cc12 cc13 cc2a cc2b cc2c cc21 cc22 cc23 cc3a cc3b cc3c cc31 cc32 cc33 c1aa c1ab c1ac c1a1 c1a2 c1a3 c1ba c1bb c1bc c1b1 c1b2 c1b3 c1ca c1cb c1cc c1c1 c1c2 c1c3 c11a c11b c11c c111 c112 c113 c12a c12b c12c c121 c122 c123 c13a c13b c13c c131 c132 c133 c2aa c2ab c2ac c2a1 c2a2 c2a3 c2ba c2bb c2bc c2b1 c2b2 c2b3 c2ca c2cb c2cc c2c1 c2c2 c2c3 c21a c21b c21c c211 c212 c213 c22a c22b c22c c221 c222 c223 c23a c23b c23c c231 c232 c233 c3aa c3ab c3ac c3a1 c3a2 c3a3 c3ba c3bb c3bc c3b1 c3b2 c3b3 c3ca c3cb c3cc c3c1 c3c2 c3c3 c31a c31b c31c c311 c312 c313 c32a c32b c32c c321 c322 c323 c33a c33b c33c c331 c332 c333 1aaa 1aab 1aac 1aa1 1aa2 1aa3 1aba 1abb 1abc 1ab1 1ab2 1ab3 1aca 1acb 1acc 1ac1 1ac2 1ac3 1a1a 1a1b 1a1c 1a11 1a12 1a13 1a2a 1a2b 1a2c 1a21 1a22 1a23 1a3a 1a3b 1a3c 1a31 1a32 1a33 1baa 1bab 1bac 1ba1 1ba2 1ba3 1bba 1bbb 1bbc 1bb1 1bb2 1bb3 1bca 1bcb 1bcc 1bc1 1bc2 1bc3 1b1a 1b1b 1b1c 1b11 1b12 1b13 1b2a 1b2b 1b2c 1b21 1b22 1b23 1b3a 1b3b 1b3c 1b31 1b32 1b33 1caa 1cab 1cac 1ca1 1ca2 1ca3 1cba 1cbb 1cbc 1cb1 1cb2 1cb3 1cca 1ccb 1ccc 1cc1 1cc2 1cc3 1c1a 1c1b 1c1c 1c11 1c12 1c13 1c2a 1c2b 1c2c 1c21 1c22 1c23 1c3a 1c3b 1c3c 1c31 1c32 1c33 11aa 11ab 11ac 11a1 11a2 11a3 11ba 11bb 11bc 11b1 11b2 11b3 11ca 11cb 11cc 11c1 11c2 11c3 111a 111b 111c 1111 1112 1113 112a 112b 112c 1121 1122 1123 113a 113b 113c 1131 1132 1133 12aa 12ab 12ac 12a1 12a2 12a3 12ba 12bb 12bc 12b1 12b2 12b3 12ca 12cb 12cc 12c1 12c2 12c3 121a 121b 121c 1211 1212 1213 122a 122b 122c 1221 1222 1223 123a 123b 123c 1231 1232 1233 13aa 13ab 13ac 13a1 13a2 13a3 13ba 13bb 13bc 13b1 13b2 13b3 13ca 13cb 13cc 13c1 13c2 13c3 131a 131b 131c 1311 1312 1313 132a 132b 132c 1321 1322 1323 133a 133b 133c 1331 1332 1333 2aaa 2aab 2aac 2aa1 2aa2 2aa3 2aba 2abb 2abc 2ab1 2ab2 2ab3 2aca 2acb 2acc 2ac1 2ac2 2ac3 2a1a 2a1b 2a1c 2a11 2a12 2a13 2a2a 2a2b 2a2c 2a21 2a22 2a23 2a3a 2a3b 2a3c 2a31 2a32 2a33 2baa 2bab 2bac 2ba1 2ba2 2ba3 2bba 2bbb 2bbc 2bb1 2bb2 2bb3 2bca 2bcb 2bcc 2bc1 2bc2 2bc3 2b1a 2b1b 2b1c 2b11 2b12 2b13 2b2a 2b2b 2b2c 2b21 2b22 2b23 2b3a 2b3b 2b3c 2b31 2b32 2b33 2caa 2cab 2cac 2ca1 2ca2 2ca3 2cba 2cbb 2cbc 2cb1 2cb2 2cb3 2cca 2ccb 2ccc 2cc1 2cc2 2cc3 2c1a 2c1b 2c1c 2c11 2c12 2c13 2c2a 2c2b 2c2c 2c21 2c22 2c23 2c3a 2c3b 2c3c 2c31 2c32 2c33 21aa 21ab 21ac 21a1 21a2 21a3 21ba 21bb 21bc 21b1 21b2 21b3 21ca 21cb 21cc 21c1 21c2 21c3 211a 211b 211c 2111 2112 2113 212a 212b 212c 2121 2122 2123 213a 213b 213c 2131 2132 2133 22aa 22ab 22ac 22a1 22a2 22a3 22ba 22bb 22bc 22b1 22b2 22b3 22ca 22cb 22cc 22c1 22c2 22c3 221a 221b 221c 2211 2212 2213 222a 222b 222c 2221 2222 2223 223a 223b 223c 2231 2232 2233 23aa 23ab 23ac 23a1 23a2 23a3 23ba 23bb 23bc 23b1 23b2 23b3 23ca 23cb 23cc 23c1 23c2 23c3 231a 231b 231c 2311 2312 2313 232a 232b 232c 2321 2322 2323 233a 233b 233c 2331 2332 2333 3aaa 3aab 3aac 3aa1 3aa2 3aa3 3aba 3abb 3abc 3ab1 3ab2 3ab3 3aca 3acb 3acc 3ac1 3ac2 3ac3 3a1a 3a1b 3a1c 3a11 3a12 3a13 3a2a 3a2b 3a2c 3a21 3a22 3a23 3a3a 3a3b 3a3c 3a31 3a32 3a33 3baa 3bab 3bac 3ba1 3ba2 3ba3 3bba 3bbb 3bbc 3bb1 3bb2 3bb3 3bca 3bcb 3bcc 3bc1 3bc2 3bc3 3b1a 3b1b 3b1c 3b11 3b12 3b13 3b2a 3b2b 3b2c 3b21 3b22 3b23 3b3a 3b3b 3b3c 3b31 3b32 3b33 3caa 3cab 3cac 3ca1 3ca2 3ca3 3cba 3cbb 3cbc 3cb1 3cb2 3cb3 3cca 3ccb 3ccc 3cc1 3cc2 3cc3 3c1a 3c1b 3c1c 3c11 3c12 3c13 3c2a 3c2b 3c2c 3c21 3c22 3c23 3c3a 3c3b 3c3c 3c31 3c32 3c33 31aa 31ab 31ac 31a1 31a2 31a3 31ba 31bb 31bc 31b1 31b2 31b3 31ca 31cb 31cc 31c1 31c2 31c3 311a 311b 311c 3111 3112 3113 312a 312b 312c 3121 3122 3123 313a 313b 313c 3131 3132 3133 32aa 32ab 32ac 32a1 32a2 32a3 32ba 32bb 32bc 32b1 32b2 32b3 32ca 32cb 32cc 32c1 32c2 32c3 321a 321b 321c 3211 3212 3213 322a 322b 322c 3221 3222 3223 323a 323b 323c 3231 3232 3233 33aa 33ab 33ac 33a1 33a2 33a3 33ba 33bb 33bc 33b1 33b2 33b3 33ca 33cb 33cc 33c1 33c2 33c3 331a 331b 331c 3311 3312 3313 332a 332b 332c 3321 3322 3323 333a 333b 333c 3331 3332 3333

Una cosa que es segura es que cualquiera que sea el uso de algo para esto, la mejor complejidad de tiempo para la generación de todos los números es alrededor de O ((n ^ m + 1) / (n-1)) (Suponiendo que no esté utilizando cualquier programación en paralelo. (Donde n es el tamaño de la matriz, m es la longitud máxima).

Para lo cual cualquiera de los algo antes mencionados conviene mejor.

Una solución PHP no recursiva basada en el algoritmo de conteo simple, con tantos dígitos posibles como la matriz $letters tiene elementos. Entonces, para una matriz de 5 elementos, que tiene una longitud máxima de 3, la matriz de conteo tiene 1 (primero) a 3 (extremo) elementos, como

0, 1, ..., 4 then 00, 01, ..., 04, 10, ... 14, ... 44

Cuando 00 es array(0,0) (en realidad, para optimizar el bucle, el conteo es como 00, 10, 20, ..., 34, 44 )

Luego, la cadena se construye a partir de esa matriz de ''conteo''.

<?php function andcounting($letters, $len) { $lastindex = count($letters) - 1; $n = array(0); // counting array while(true) { // display current result for ($i=count($n)-1 ; $i>=0 ; $i--) echo $letters[$n[$i]]; echo "/n"; // increment $n for ($i=count($n)-1 ; $i>=0 ; $i--) { if (++$n[$i] <= $lastindex) break; $n[$i] = 0; } // check if need to add a dim (or exit) if ($i < 0) { if (count($n) == $len) break; $n[] = 0; } } }

Ejecutando la funcion

andcounting( array(''a'',''b'',''c'',''d'',''e''), 3);

que da (de izquierda a derecha y de arriba a abajo )

a b c d e aa ba ca da ea ab bb cb db eb ac bc cc dc ec ad bd cd dd ed ae be ce de ee aaa baa caa daa eaa aba bba cba dba eba aca bca cca dca eca ada bda cda dda eda aea bea cea dea eea aab bab cab dab eab abb bbb cbb dbb ebb acb bcb ccb dcb ecb adb bdb cdb ddb edb aeb beb ceb deb eeb aac bac cac dac eac abc bbc cbc dbc ebc acc bcc ccc dcc ecc adc bdc cdc ddc edc aec bec cec dec eec aad bad cad dad ead abd bbd cbd dbd ebd acd bcd ccd dcd ecd add bdd cdd ddd edd aed bed ced ded eed aae bae cae dae eae abe bbe cbe dbe ebe ace bce cce dce ece ade bde cde dde ede aee bee cee dee eee

Yo iría con una solución recursiva.
"Adivina" cuál es el primer elemento y repite sobre los siguientes elementos.
Repita para todas las conjeturas posibles.

pseudo codigo

findCombinations(array, candidate, length): //base clause: if (candidate.length == length): return for each i from 0to array.length: //i is the next char to add candidate.append(array[i]) //print the candidate, since it is a unique permutation smaller then length: print candidate //recursively find permutations for the remianing elements findCombinations(array,candidate,length) //clean up candidate.removeLasElement()

Código Java:

private static void findCombinations(char[] array, StringBuilder candidate, int length) { //base clause: if (candidate.length() == length) return; for (int i = 0; i < array.length; i++) { //i is the next char to add candidate.append(array[i]); //print the candidate, since it is a unique permutation smaller then length: System.out.println(candidate); //recursively find permutations for the remianing elements findCombinations(array,candidate,length); //clean up candidate.deleteCharAt(candidate.length()-1); } } public static void findCombinations(char[] array,int length) { findCombinations(array, new StringBuilder(), length); }

Invocando

char[] arr = "abcde".toCharArray(); findCombinations(arr, 3);

resultados en:

a aa aaa aab aac aad aae ab aba abb abc abd abe ac aca acb acc acd ace ad ada adb adc add ade ae aea aeb aec aed aee b ba baa bab bac bad bae bb bba bbb bbc bbd bbe bc bca bcb bcc bcd bce bd bda bdb bdc bdd bde be bea beb bec bed bee c ca caa cab cac cad cae cb cba cbb cbc cbd cbe cc cca ccb ccc ccd cce cd cda cdb cdc cdd cde ce cea ceb cec ced cee d da daa dab dac dad dae db dba dbb dbc dbd dbe dc dca dcb dcc dcd dce dd dda ddb ddc ddd dde de dea deb dec ded dee e ea eaa eab eac ead eae eb eba ebb ebc ebd ebe ec eca ecb ecc ecd ece ed eda edb edc edd ede ee eea eeb eec eed eee

Solución

function combinationsByLenth($arr, $len) { $combinations = []; $select = array_fill(0, $len, 0); $selectCount = count($select); $arrCount = count($arr); $possibleCombinations = pow($arrCount, $selectCount); while ($possibleCombinations-- > 0) { $combination = ''''; foreach ($select as $index) { $combination .= $arr[$index]; } $combinations[] = $combination; for ($i = $selectCount - 1; $i >= 0; $i--) { if ($select[$i] !== ($arrCount - 1)) { $select[$i]++; break; } else { $select[$i] = 0; } } } return $combinations; } function combinationsByMinMax($arr, $min, $max) { $combinations = []; for ($i = $min; $i <= $max; $i++) { $combinations = array_merge($combinations, combinationsByLenth($arr, $i)); } return $combinations; } print_r(combinationsByMinMax($arr, 1, 5));

Salida

Array ( [0] => a [1] => b [2] => c [3] => 1 [4] => 2 [5] => 3 [6] => aa [7] => ab [8] => ac [9] => a1 ... [9320] => 3332c [9321] => 33321 [9322] => 33322 [9323] => 33323 [9324] => 3333a [9325] => 3333b [9326] => 3333c [9327] => 33331 [9328] => 33332 [9329] => 33333 )

Razón fundamental

  • Evite las soluciones recursivas para este tipo de problema en PHP (tenga en cuenta que me gusta la recursión en lenguajes optimizados para manejarlo mejor) para evitar problemas de apilamiento a medida que aumenta la longitud.
  • Divida la función en dos funciones separadas, una que implemente la longitud mínima y máxima, y ​​otra que obtenga las combinaciones posibles para una longitud específica para promover la reutilización y la claridad.
  • Limite las llamadas a funciones dentro de las 2 funciones tanto como sea posible para mejorar el rendimiento (¡este algoritmo se hace muy rápido!)

Cómo desarrollé esta solución

Comencé con una función que manejaba el caso específico de combinaciones de longitud 5, refactorizado para generalizar el algoritmo, refactorizado para generalizar el algoritmo, etc. He puesto una idea rápida para que pueda ver las iteraciones para llegar a este trabajo La versión como estudio de caso de cómo abordar la construcción de este tipo de algoritmo:

https://gist.github.com/AdamJonR/5278480

Aquí hay una solución simple.

Suposición:

$source = array( ''a'', ''b'', ''c'', ''1'', ''2'', ''3'' );

Ejemplo 1

$c = new FindCombination($source); echo $c->find(4,true); //returns all resul in json echo count($c), PHP_EOL; //returns total

Ejemplo 2

Si quieres usarlo ordenado.

echo $c->find(4,true);

Salida

[ "1", "2", "3", "a", "b", "c", "12", "13", "1a", "1b", "1c", "21", "23", "2a", "2b", "2c", "31", "32", "3a", "3b", "3c", "a1", "a2", "a3", "ab", "ac", "b1", "b2", "b3", "ba", "bc", "c1", "c2", "c3", "ca", "cb", "123", "12a", "12b", "12c", "132", "13a", "13b", "13c", "1a2", "1a3", "1ab", "1ac", "1b2", "1b3", "1ba", "1bc", "1c2", "1c3", "1ca", "1cb", "213", "21a", "21b", "21c", "231", "23a", "23b", "23c", "2a1", "2a3", "2ab", "2ac", "2b1", "2b3", "2ba", "2bc", "2c1", "2c3", "2ca", "2cb", "312", "31a", "31b", "31c", "321", "32a", "32b", "32c", "3a1", "3a2", "3ab", "3ac", "3b1", "3b2", "3ba", "3bc", "3c1", "3c2", "3ca", "3cb", "a12", "a13", "a1b", "a1c", "a21", "a23", "a2b", "a2c", "a31", "a32", "a3b", "a3c", "ab1", "ab2", "ab3", "abc", "ac1", "ac2", "ac3", "acb", "b12", "b13", "b1a", "b1c", "b21", "b23", "b2a", "b2c", "b31", "b32", "b3a", "b3c", "ba1", "ba2", "ba3", "bac", "bc1", "bc2", "bc3", "bca", "c12", "c13", "c1a", "c1b", "c21", "c23", "c2a", "c2b", "c31", "c32", "c3a", "c3b", "ca1", "ca2", "ca3", "cab", "cb1", "cb2", "cb3", "cba", "123a", "123b", "123c", "12a3", "12ab", "12ac", "12b3", "12ba", "12bc", "12c3", "12ca", "12cb", "132a", "132b", "132c", "13a2", "13ab", "13ac", "13b2", "13ba", "13bc", "13c2", "13ca", "13cb", "1a23", "1a2b", "1a2c", "1a32", "1a3b", "1a3c", "1ab2", "1ab3", "1abc", "1ac2", "1ac3", "1acb", "1b23", "1b2a", "1b2c", "1b32", "1b3a", "1b3c", "1ba2", "1ba3", "1bac", "1bc2", "1bc3", "1bca", "1c23", "1c2a", "1c2b", "1c32", "1c3a", "1c3b", "1ca2", "1ca3", "1cab", "1cb2", "1cb3", "1cba", "213a", "213b", "213c", "21a3", "21ab", "21ac", "21b3", "21ba", "21bc", "21c3", "21ca", "21cb", "231a", "231b", "231c", "23a1", "23ab", "23ac", "23b1", "23ba", "23bc", "23c1", "23ca", "23cb", "2a13", "2a1b", "2a1c", "2a31", "2a3b", "2a3c", "2ab1", "2ab3", "2abc", "2ac1", "2ac3", "2acb", "2b13", "2b1a", "2b1c", "2b31", "2b3a", "2b3c", "2ba1", "2ba3", "2bac", "2bc1", "2bc3", "2bca", "2c13", "2c1a", "2c1b", "2c31", "2c3a", "2c3b", "2ca1", "2ca3", "2cab", "2cb1", "2cb3", "2cba", "312a", "312b", "312c", "31a2", "31ab", "31ac", "31b2", "31ba", "31bc", "31c2", "31ca", "31cb", "321a", "321b", "321c", "32a1", "32ab", "32ac", "32b1", "32ba", "32bc", "32c1", "32ca", "32cb", "3a12", "3a1b", "3a1c", "3a21", "3a2b", "3a2c", "3ab1", "3ab2", "3abc", "3ac1", "3ac2", "3acb", "3b12", "3b1a", "3b1c", "3b21", "3b2a", "3b2c", "3ba1", "3ba2", "3bac", "3bc1", "3bc2", "3bca", "3c12", "3c1a", "3c1b", "3c21", "3c2a", "3c2b", "3ca1", "3ca2", "3cab", "3cb1", "3cb2", "3cba", "a123", "a12b", "a12c", "a132", "a13b", "a13c", "a1b2", "a1b3", "a1bc", "a1c2", "a1c3", "a1cb", "a213", "a21b", "a21c", "a231", "a23b", "a23c", "a2b1", "a2b3", "a2bc", "a2c1", "a2c3", "a2cb", "a312", "a31b", "a31c", "a321", "a32b", "a32c", "a3b1", "a3b2", "a3bc", "a3c1", "a3c2", "a3cb", "ab12", "ab13", "ab1c", "ab21", "ab23", "ab2c", "ab31", "ab32", "ab3c", "abc1", "abc2", "abc3", "ac12", "ac13", "ac1b", "ac21", "ac23", "ac2b", "ac31", "ac32", "ac3b", "acb1", "acb2", "acb3", "b123", "b12a", "b12c", "b132", "b13a", "b13c", "b1a2", "b1a3", "b1ac", "b1c2", "b1c3", "b1ca", "b213", "b21a", "b21c", "b231", "b23a", "b23c", "b2a1", "b2a3", "b2ac", "b2c1", "b2c3", "b2ca", "b312", "b31a", "b31c", "b321", "b32a", "b32c", "b3a1", "b3a2", "b3ac", "b3c1", "b3c2", "b3ca", "ba12", "ba13", "ba1c", "ba21", "ba23", "ba2c", "ba31", "ba32", "ba3c", "bac1", "bac2", "bac3", "bc12", "bc13", "bc1a", "bc21", "bc23", "bc2a", "bc31", "bc32", "bc3a", "bca1", "bca2", "bca3", "c123", "c12a", "c12b", "c132", "c13a", "c13b", "c1a2", "c1a3", "c1ab", "c1b2", "c1b3", "c1ba", "c213", "c21a", "c21b", "c231", "c23a", "c23b", "c2a1", "c2a3", "c2ab", "c2b1", "c2b3", "c2ba", "c312", "c31a", "c31b", "c321", "c32a", "c32b", "c3a1", "c3a2", "c3ab", "c3b1", "c3b2", "c3ba", "ca12", "ca13", "ca1b", "ca21", "ca23", "ca2b", "ca31", "ca32", "ca3b", "cab1", "cab2", "cab3", "cb12", "cb13", "cb1a", "cb21", "cb23", "cb2a", "cb31", "cb32", "cb3a", "cba1", "cba2", "cba3" ]

Ejemplo 3

Puedes recorrer el resultado

$c = new FindCombination($source); foreach ( $c->find(4, true) as $v ) { echo $v . "|"; }

Clase utilizada

class FindCombination implements IteratorAggregate, JsonSerializable, Countable { private $source; private $sink = array(); private $max = 0; function __construct(&$source) { $this->source = $source; } public function jsonSerialize() { return json_encode($this->sink, 128); } public function getIterator() { return new ArrayIterator($this->sink); } public function count() { return count($this->sink); } public function __toString() { return $this->jsonSerialize(); } public function find($max = 0, $sort = false) { $this->sink = array(); // reset sink $this->max = $max; $this->parse($this->source); if ($sort) { usort($this->sink, function ($a, $b) { $al = strlen($a); $bl = strlen($b); return $al == $bl ? strcmp($a, $b) : strcmp($al, $bl); }); } return $this; } private function parse($source, $tempString = "") { if ($tempString != "") $this->sink[] = $tempString; for($i = 0; $i < count($source); $i ++) { $copy = $source; $elem = array_splice($copy, $i, 1); $tempModified = $tempString . $elem[0]; if (strlen($tempModified) > $this->max && $this->max > 0) continue; if (count($copy) > 0) { $this->parse($copy, $tempModified); } else { $this->sink[] = $tempModified; } } } }

El producto acumulado del conjunto para k veces con un conjunto S que está vacío inicialmente producirá todas las permutaciones hasta k-long, con n = | S | ..

Tiempo: O (kn ^ 2)

Espacio: O (kn ^ 2)

// Enumerate all permutations, PHP // by Khaled A Khunaifer, 25/3/2013 function setProduct($a, $b) { $arr = array(); foreach ($a as $s) { foreach ($b as $t) { $arr[] = $s . $t; } } return $arr; } function enumerate ($arrary, $maxLen) { $enumeration = array(); for (var $i = 1; $i <= $maxLen; $i++) { $enumeration += setProduct($enumeration, $array); } }

Es más tranquilo de código que el algoritmo :) pero funciona! Me pareció útil tener iterador de secuencia.

$characters = implode('''', $letters_array); // string as character set $seq = new Sequence($characters, $min_length, $max_length); while (($s = $seq->fetch()) !== false) { echo $s . "/n"; }

Esta es una clase:

<?php class Sequence { private $_set, $_min, $_max; private $_string; public function __construct($set, $min, $max) { $this->_set = $set; $this->_min = $min; $this->_max = $max; $this->_string = str_repeat($set{0}, $min); } public function fetch() { // get current value and calculate next one $result = $this->_string; // while current value is not "finish mark" if ($this->_string !== false) { $l = strlen($this->_string); // move from left to right and try to "increment" characters for ($p = 0; $p < $l; ++$p) { $c = $this->_string{$p}; $i = strpos($this->_set, $c); if ($i < strlen($this->_set) - 1) { $this->_string{$p} = $this->_set{++$i}; break; } // we''ve try all characters here, drop this and go to the next one $this->_string{$p} = $this->_set{0}; } // if string is ended (cycle not breaked) if ($p == $l) { // $l is new string length. if it''s too long, make "finish mark" if ($l > $this->_max) $this->_string = false; else $this->_string .= $this->_set{0}; } } return $result; } }

El resultado es

a b c 1 2 3 aa ba ... 23333 33333

Le sugiero que encuentre una implementación de la función itertools.product de pythons en php. (O simplemente copie la implementación usted mismo).

El siguiente código obtiene todas las permutaciones de la longitud especificada. Usted querría longitudes 1, 2, 3, 4.

La preocupación final es que no hay caracteres duplicados, así que puedes agregar "letters = set (letters)" solo para asegurarte.

>>> letters = "abc123" >>> length = 3 >>> from itertools import product >>> dimensions = [letters]*length >>> for point in product(*dimensions): ... print "".join(point) ... aaa aab aac aa1 aa2 aa3 aba abb abc ab1 ab2 ab3 aca acb acc ac1 ac2 ac3 a1a a1b a1c a11 a12 a13 a2a a2b a2c a21 a22 a23 a3a a3b a3c a31 a32 a33 baa bab bac ba1 ba2 ba3 bba bbb bbc bb1 bb2 bb3 bca bcb bcc bc1 bc2 bc3 b1a b1b b1c b11 b12 b13 b2a b2b b2c b21 b22 b23 b3a b3b b3c b31 b32 b33 caa cab cac ca1 ca2 ca3 cba cbb cbc cb1 cb2 cb3 cca ccb ccc cc1 cc2 cc3 c1a c1b c1c c11 c12 c13 c2a c2b c2c c21 c22 c23 c3a c3b c3c c31 c32 c33 1aa 1ab 1ac 1a1 1a2 1a3 1ba 1bb 1bc 1b1 1b2 1b3 1ca 1cb 1cc 1c1 1c2 1c3 11a 11b 11c 111 112 113 12a 12b 12c 121 122 123 13a 13b 13c 131 132 133 2aa 2ab 2ac 2a1 2a2 2a3 2ba 2bb 2bc 2b1 2b2 2b3 2ca 2cb 2cc 2c1 2c2 2c3 21a 21b 21c 211 212 213 22a 22b 22c 221 222 223 23a 23b 23c 231 232 233 3aa 3ab 3ac 3a1 3a2 3a3 3ba 3bb 3bc 3b1 3b2 3b3 3ca 3cb 3cc 3c1 3c2 3c3 31a 31b 31c 311 312 313 32a 32b 32c 321 322 323 33a 33b 33c 331 332 333