Générer des permutations en utilisant bash

Question

est-il possible d'écrire un script bash qui peut lire dans chaque ligne d'un fichier et générer des permutations (sans répétition) pour chacun? Utiliser awk/perl est bien.

File 
---- 
ab 
abc 


Output 
------ 
ab 
ba 
abc 
acb 
bac 
bca 
cab 
cba 

Answer 1

bash pur (en utilisant local, plus rapide, mais ne peut pas battre l'autre réponse à l'aide awk ci-dessous, ou Python ci-dessous):

perm() { 
    local items="$1" 
    local out="$2" 
    local i 
    [[ "$items" == "" ]] && echo "$out" && return 
    for ((i=0; i<${#items}; i++)) ; do 
    perm "${items:0:i}${items:i+1}" "$out${items:i:1}" 
    done 
    } 
while read line ; do perm $line ; done < File 

bash pur (en utilisant sous-shell, beaucoup plus lent):

perm() { 
    items="$1" 
    out="$2" 
    [[ "$items" == "" ]] && echo "$out" && return 
    for ((i=0; i<${#items}; i++)) ; do 
    (perm "${items:0:i}${items:i+1}" "$out${items:i:1}") 
    done 
    } 
while read line ; do perm $line ; done < File 

Depuis Perl est mentionné asker bien, je pense que Python 2.6 +/3.X est très bien aussi:

python -c "from itertools import permutations as p ; print('\n'.join([''.join(item) for line in open('File') for item in p(line[:-1])]))" 

Pour Python 2.5 +/3.X:

#!/usr/bin/python2.5 

# http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python/104436#104436 
def all_perms(str): 
    if len(str) <=1: 
     yield str 
    else: 
     for perm in all_perms(str[1:]): 
      for i in range(len(perm)+1): 
       #nb str[0:1] works in both string and list contexts 
       yield perm[:i] + str[0:1] + perm[i:] 

print('\n'.join([''.join(item) for line in open('File') for item in all_perms(line[:-1])])) 

Sur mon ordinateur à l'aide d'un plus grand fichier de test:

First Python code 
    Python 2.6:  0.038s 
    Python 3.1:  0.052s 
Second Python code 
    Python 2.5/2.6: 0.055s 
    Python 3.1:  0.072s 
awk:    0.332s 
Bash (local):  2.058s 
Bash (subshell): 22+s 

Answer 2

Voir le Perl Cookbook pour des exemples de permutation. Ils sont axés sur les mots/nombres, mais un simple split()/join() sur votre exemple ci-dessus suffira.

Answer 3

$ ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join}' file # ver 1.9.1 

Answer 4

Une version plus rapide en utilisant awk

function permute(s, st,  i, j, n, tmp) { 
    n = split(s, item,//) 
    if (st > n) { print s; return } 
    for (i=st; i<=n; i++) { 
     if (i != st) { 
     tmp = item[st]; item[st] = item[i]; item[i] = tmp 
     nextstr = item[1] 
     for (j=2; j<=n; j++) nextstr = nextstr delim item[j] 
     }else { 
      nextstr = s 
     } 
     permute(nextstr, st+1) 
     n = split(s, item, //) 
    } 
} 
{ permute($0,1) } 

utilisation

:

$ awk -f permute.awk file 

Answer 5

Utilisation du crunch util et bash:

while read a ; do crunch ${#a} ${#a} -p "$a" ; done 2> /dev/null < File 

Sortie:

ab 
ba 
abc 
acb 
bac 
bca 
cab 
cba 

Tutoriel ici https://pentestlab.blog/2012/07/12/creating-wordlists-with-crunch/

Answer 6

Bash liste de mots/Dictionnaire/générateur de permutation:

Le Le code Bash suivant génère 3 caractères permut ation sur 0-9, a-z, A-Z. Il vous donne (10 + 26 + 26)^3 = 238,328 mots en sortie.

Ce n'est pas très évolutif car vous pouvez voir que vous devez augmenter le nombre de for pour augmenter la combinaison de caractères. Il serait beaucoup plus rapide d'écrire une telle chose dans l'assemblage ou C en utilisant la récursivité pour augmenter la vitesse. Le code Bash est seulement pour la démonstration.

P.S. Vous pouvez remplir $list variable list=$(cat input.txt)

#!/bin/bash 

list=`echo {0..9} {a..z} {A..Z}` 

for c1 in $list 
do 
     for c2 in $list 
     do 
       for c3 in $list 
       do 
         echo $c1$c2$c3 
       done 
     done 
done 

EXEMPLE DE SORTIE:

000 
001 
002 
003 
004 
005 
... 
... 
... 
ZZU 
ZZV 
ZZW 
ZZX 
ZZY 
ZZZ 
[babil@quad[13:27:37][~]> wc -l t.out 
238328 t.out 

Answer 7

Parce que vous ne pouvez jamais avoir enogh cryptiques Bash-Citations:

while read s;do p="$(echo "$s"|sed -e 's/./&,/g' -e 's/,$//')";eval "printf "%s\\\\n" "$(eval 'echo "$(printf "{'"$p"'}%.0s" {0..'"$((${#s}-1))"'})"')"|grep '\(.\)\1*.*\1' -v";echo;done <f 

Il est assez rapide - au moins sur ma machine ici:

$ time while read s;do p="$(echo "$s"|sed -e 's/./&,/g' -e 's/,$//')";eval "printf "%s\\\\n" "$(eval 'echo "$(printf "{'"$p"'}%.0s" {0..'"$((${#s}-1))"'})"')"|grep '\(.\)\1*.*\1' -v";echo;done <f >/dev/null 

real 0m0.021s 
user 0m0.000s 
sys 0m0.004s 

Mais sachez que celui-ci va manger beaucoup de mémoire quand vous allez au-delà de 8 caractères ...

Answer 8

Je sais que je suis un peu en retard au jeu, mais pourquoi ne pas Brace l'expansion?

Par exemple:

echo {a..z}{0..9} 

Sorties:

a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 g0 g1 g2 g3 g4 g5 g6 g7 g8 g9 h0 h1 h2 h3 h4 h5 h6 h7 h8 h9 i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 j0 j1 j2 j3 j4 j5 j6 j7 j8 j9 k0 k1 k2 k3 k4 k5 k6 k7 k8 k9 l0 l1 l2 l3 l4 l5 l6 l7 l8 l9 m0 m1 m2 m3 m4 m5 m6 m7 m8 m9 n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 p0 p1 p2 p3 p4 p5 p6 p7 p8 p9 q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 s0 s1 s2 s3 s4 s5 s6 s7 s8 s9 t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 u0 u1 u2 u3 u4 u5 u6 u7 u8 u9 v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 z0 z1 z2 z3 z4 z5 z6 z7 z8 z9 

Un autre exemple utile:

for X in {a..z}{a..z}{0..9}{0..9}{0..9} 
    do echo $X; 
done