[PYTHON] A string permutation code that uses an algorithm that generates permutations.

The order of the given strings is changed and all are displayed. Character strings containing the same duplicated characters are processed as they are duplicated. n! Character strings are output.

C For the algorithm, I referred to "Latest Algorithm Dictionary in C Language" (written by Haruhiko Okumura) by Gijutsu-Hyoronsha. If you have a terminal C development environment, you can easily compile.

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

If you write it using permutations of itertools, it will be like this. It's a lot refreshing.

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

Execution result

$ 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

Output example of a character string containing the same character

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

Recommended Posts

A string permutation code that uses an algorithm that generates permutations.
# Function that returns the character code of a string
Convert a path string that uses a symbolic link in the middle to an absolute path
Convert a string to an image
[Python] I wrote a simple code that automatically generates AA (ASCII art)
The eval () function that calculates a string as an expression in python
Code reading of faker, a library that generates test data in Python
A code that corrects the yoon / sokuon (sokuon)
I wrote an animation that degenerates a linear system with deadly dirty code