Toutes les combinaisons possibles en C

J’essaie de trouver un algorithme efficace en C, qui me fournit toutes les combinaisons d’un jeu de caractères donné.

L’algorithme ne doit pas être récursif. Enfin, le nombre de chiffres doit être flexible. Par exemple:

char set[] = "a1"; -> a1 aa 1a 11 

J’ai seulement trouvé une solution Perl, mais elle utilise substr() . Je pense que ce n’était pas si rapide en termes de performances.

Pour la plupart des algorithmes en C, j’ai trouvé qu’il ne s’agissait que de permutations …

Un article dans un forum C ++ allemand affirme que les solutions C ++-STL sont plus rapides que les algorithmes récursifs “bruts”.

Si la taille de l’ensemble était un N fixe, ce serait simple: vous pouvez simplement avoir N for boucles, chacune nestede dans la précédente. Puisque vous ne pouvez pas faire cela et que vous ne pouvez pas utiliser la récursivité, vous devez calculer le nombre total requirejs d’itérations (il semble que ce soit N ^ M), utilisez une seule boucle, puis utilisez / et% pour calculer l’indice de tableau. de chaque caractère devrait être. Vous feriez mieux d’utiliser long aussi, car N ^ M devient gros rapidement.

Wikipedia a un code C pour le code n-aire Gray . Il devrait être convertible en votre problème en utilisant les chiffres comme décalages dans votre tableau en entrée. Vous devrez effectuer une allocation dynamic pour gérer la longueur arbitraire de votre entrée. Une approche connexe consiste à créer des boucles nestedes, dans lesquelles vous avez un tableau de compteurs de boucles aussi longs que votre entrée et un autre compteur pour lequel de ceux que vous incrémentez actuellement. Par exemple, l’impression des six chiffres de la base 6 à six chiffres doit être modifiée pour l’atsortingbution dynamic, tout en indiquant le principe suivant:

 int i; int length = 5; int max = 6; int counters[length]; for (i=0; i=0; i--) printf("%d", counters[i]); printf("\n"); for(i=0; i= length) break; } 

Python est très proche d’un pseudo-code.

Vous pouvez lire le source Python sur itertools.permutations et simplement le répliquer en C.

Voici la démo que cela fonctionne:

 #!/usr/bin/env python import itertools s='a1' print set(itertools.permutations(s*len(s), len(s))) 

Sortie:

 set([('1', '1'), ('a', '1'), ('a', 'a'), ('1', 'a')]) 

Voici un moyen encore plus simple:

 >>> s='a1' >>> ['{}{}'.format(x,y) for x in s for y in s] ['aa', 'a1', '1a', '11'] >>> s='abc' >>> ['{}{}{}'.format(x,y,z) for x in s for y in s for z in s] ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc'] 

Pour dérouler une liste, utilisez NESTED LOOPS, comme suit:

 >>> for x in s: ... for y in s: ... for z in s: ... print '{}{}{}'.format(x,y,z) 

Eh bien, je numéroter les combinaisons possibles, parcourir les nombres et convertir.

Par exemple: pour générer toutes les combinaisons de taille 3 des 10 symboles {‘0’, ‘1’, …, ‘9’}, il me faudrait une boucle de 0 à 999 et une sortie de “000” à “999”.

De la même manière (un peu), pour générer toutes les combinaisons de taille 3 des 5 symboles {‘a’, ‘b’, …, ‘e’}, je boucle de 0 à 5 * 5 * 5-1 et la sortie le numéro de boucle en base 5, mais avec les symboles fournis.

Ecrivez une fonction qui convertira un entier en un nombre hexadécimal de chaîne, puis convertira cet algorithme en un nombre de base 36 (az plus 0-9). Utilisez une boucle pour compter de 1 à (nombre de fois le nombre de chiffres) et appelez votre fonction à chaque fois.

  • 1 devient 1
  • 10 devient un
  • 35 devient z
  • 36 devient 10
  • 46 devient 1a