Un code de tri de chaîne qui utilise un algorithme qui génère une permutation.

L'ordre des chaînes de caractères données est modifié et toutes sont affichées. Les chaînes de caractères contenant les mêmes caractères dupliqués sont traitées lors de leur duplication. n! Des chaînes de caractères sont générées.

C Pour l'algorithme, j'ai fait référence au «Dernier dictionnaire d'algorithmes en langage C» (écrit par Haruhiko Okumura) par Technical Review. Si vous avez un environnement de développement terminal C, vous pouvez facilement compiler.

to compile: cc kuu.c -o kuu Usage: kuu word

kuu.c


#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>
#define	TRUE	1
#define	FALSE	0
int		N;
int		p[256];
int		count;
int		ok[257];
char	word[256];

void	show(void) {
	int	i;
	
	count++; printf("%12d: ",count);
	for(i=0;i<N;i++) {
		printf("%c",word[p[i]-1]);
		}
	printf("\n");
}

void	put(int pos,int k) {
	int j;
	p[pos]=k;
	if (pos==N-1) show();
	else {
		ok[k]=FALSE;
		for(j=1;j<=N;j++)
			if(ok[j]) put(pos+1,j);
		ok[k]=TRUE;
		}
}

void genperm1(void)
{
	int	k;

	count=0;
	for(k=1;k<=N;k++) ok[k]=TRUE;
	for(k=1;k<=N;k++) put(0,k);

}

int	main(int argc,char *argv[])
{
	if (argc!=2) {
		fprintf(stderr,"Usage kuu word\n");
		exit(1);
		}
	sscanf(argv[1],"%s",word);
	N=strlen(word);
	genperm1();
}

python

Si vous l'écrivez en utilisant des permutations d'itertools, ce sera comme ça. C'est assez rafraîchissant.

kuu.py


#!/usr/bin/python3
import sys
import itertools

word = sys.argv[1]
i=1
for p in itertools.permutations(word, len(word)):
    print("%8d" % i, ':', ''.join(p))
    i+=1

Résultat d'exécution

$ kuu alice
           1: alice
           2: aliec
           3: alcie
           4: alcei
           5: aleic
           6: aleci
           7: ailce
           8: ailec
           9: aicle
          10: aicel
          11: aielc
          12: aiecl
          13: aclie
          14: aclei
          15: acile
          16: aciel
          17: aceli
          18: aceil
          19: aelic
          20: aelci
          21: aeilc
          22: aeicl
          23: aecli
          24: aecil
          25: laice
          26: laiec
          27: lacie
          28: lacei
          29: laeic
          30: laeci
          31: liace
          32: liaec
          33: licae
          34: licea
          35: lieac
          36: lieca
          37: lcaie
          38: lcaei
          39: lciae
          40: lciea
          41: lceai
          42: lceia
          43: leaic
          44: leaci
          45: leiac
          46: leica
          47: lecai
          48: lecia
          49: ialce
          50: ialec
          51: iacle
          52: iacel
          53: iaelc
          54: iaecl
          55: ilace
          56: ilaec
          57: ilcae
          58: ilcea
          59: ileac
          60: ileca
          61: icale
          62: icael
          63: iclae
          64: iclea
          65: iceal
          66: icela
          67: iealc
          68: ieacl
          69: ielac
          70: ielca
          71: iecal
          72: iecla
          73: calie
          74: calei
          75: caile
          76: caiel
          77: caeli
          78: caeil
          79: claie
          80: claei
          81: cliae
          82: cliea
          83: cleai
          84: cleia
          85: ciale
          86: ciael
          87: cilae
          88: cilea
          89: cieal
          90: ciela
          91: ceali
          92: ceail
          93: celai
          94: celia
          95: ceial
          96: ceila
          97: ealic
          98: ealci
          99: eailc
         100: eaicl
         101: eacli
         102: eacil
         103: elaic
         104: elaci
         105: eliac
         106: elica
         107: elcai
         108: elcia
         109: eialc
         110: eiacl
         111: eilac
         112: eilca
         113: eical
         114: eicla
         115: ecali
         116: ecail
         117: eclai
         118: eclia
         119: ecial
         120: ecila

Exemple de sortie d'une chaîne de caractères contenant le même caractère

$ kuu kuu
           1: kuu
           2: kuu
           3: uku
           4: uuk
           5: uku
           6: uuk

Recommended Posts

Un code de tri de chaîne qui utilise un algorithme qui génère une permutation.
#Une fonction qui renvoie le code de caractère d'une chaîne de caractères
Convertir une chaîne de chemin qui utilise un lien symbolique au milieu en un chemin absolu
Convertir une chaîne en image
[Python] J'ai écrit un code simple qui génère automatiquement AA (Ascii Art)
Fonction Eval () qui calcule une chaîne de caractères comme expression en python
Lecture de code de faker, une bibliothèque qui génère des données de test en Python
J'ai écrit une animation que le système linéaire rétrécit avec du code sale mortel