Генерация перестановок с использованием Bash

Можно ли написать сценарий Bash, который может читать в каждой строке из файла и генерировать перестановки (без повторений) для каждого? Использование awk / perl - это нормально.

File
----
ab
abc


Output
------
ab
ba
abc
acb
bac
bca
cab
cba
 user19177602 окт. 2010 г., 16:20
Какова цель этого?
 siliconpi04 окт. 2010 г., 09:46
Мне нравится избивать вещи ...: P

Ответы на вопрос(8)

Perl Cookbook для примеров перестановки. Они ориентированы на слово / число, но простыsplit()/join() на вашем приведенном выше примере будет достаточно.

 Brian Agnew19 февр. 2013 г., 10:11
Почему проголосовали? ОП специально говорит, что Perl является приемлемым решением

Список слов Bash / словарь / генератор перестановок:

Следующий код Bash генерирует 3-символьную перестановку над 0-9, a-z, A-Z. Это дает вам (10 + 26 + 26) ^ 3 = 238,328 слов в выводе.

Это не очень масштабируемо, так как вы видите, что вам нужно увеличить количествоfor цикл для увеличения символов в комбинации. Было бы намного быстрее написать такую ​​вещь в ассемблере или C, используя рекурсию для увеличения скорости. Код Bash предназначен только для демонстрации.

Постскриптум Вы можете заполнить$list переменная с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

ОБРАЗЕЦ ВЫХОДА:

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

iners:

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

Это довольно быстро - по крайней мере, на моей машине здесь:

$ 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

Но имейте в виду, что этот будет съедать много памяти, когда вы выходите за рамки 8 символов ...

Например:

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

Выходы:

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

Еще один полезный пример:

for X in {a..z}{a..z}{0..9}{0..9}{0..9}
    do echo $X;
done
 SigmaX12 июл. 2018 г., 14:29
@Aviadisto Это удалит дубликаты (если я вас понимаю), но я был обеспокоен повторением элементов в каждой перестановке (что является чем-то другим). Однако, глядя на этот ответ еще раз, я понимаю, что он вычисляет перекрестное произведение двух множеств, а не перестановку. Так что это не отвечает ни на оригинальный вопрос, ни на то, что я искал! Я надеюсь, что я не использовал этот код где-то важно, смеется.
 SigmaX20 февр. 2015 г., 22:03
Это круто, но это создает перестановкус повторением (что, по совпадению, это то, что я пришел сюда в поисках.) Вопрос, кажется, о простых перестановках, которые не допускают повторения.
 Aviadisto11 июл. 2018 г., 13:43
@SigmaX, тогда вы можете передать конечный результат через сортировку | Uniq, например echo {a..z} {0..9} | tr '' '\ n' | сортировать | уник
Решение Вопроса

Pure Bash (используяlocal, быстрее, но не может опередить другой ответ, используя awk ниже или Python ниже):

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 (используя subshell, намного медленнее):

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

Поскольку Asker упомянул Perl, я думаю, что Python 2.6 + / 3.X тоже подойдет:

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

Для 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])]))

На моем компьютере используется тестовый файл большего размера:

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
 ShellFish16 апр. 2015 г., 01:19
Где твоеawk код?
 ghostdog7402 окт. 2010 г., 17:58
хороший удар, но слишком медленный, если длина становится больше
 Dennis Williamson02 окт. 2010 г., 17:55
Вместоcat File | while делатьdone < File.
 ShellFish16 апр. 2015 г., 08:50
Ах, я вижу, отличный пост, хотя!
 livibetter02 окт. 2010 г., 18:14
@ Денис, спасибо за советы, ответ отредактировал.
 siliconpi05 окт. 2010 г., 11:55
Круто - не думал, что это возможно!
 Dennis Williamson02 окт. 2010 г., 18:02
Кроме того, вы можете сделать математику в разрезании массива без$(()) и вы можете опустить знаки доллара: `(perm" $ {items: 0: i} $ {items: i + 1} "" $ out $ {items: i: 1}) ""
 livibetter03 окт. 2010 г., 07:32
@ user131527, какую версию Python вы используете? Если это 2,5, то этот результат неверен. Мой оригинальный код на Python не работает для 2.5 и 3.1, и он работает медленнее, чем awk, но он некорректен. Я обновил код, и все они намного быстрее, чем awk.
 ghostdog7403 окт. 2010 г., 00:20
на моем компьютере awk всегда самый быстрый.
 livibetter16 апр. 2015 г., 08:42
@ShellFish Я имел в виду ghostdog74'sответ который написан на авк. Как вы можете видеть, мы обсуждали некоторые вопросы выше, поэтому я добавил временной тест для его или ее кода Awk. Я должен был быть более ясным, когда я редактировал свой ответ.
$ ruby -ne '$_.chomp.chars.to_a.permutation{|x| puts x.join}' file # ver 1.9.1
 siliconpi02 окт. 2010 г., 17:39
выдает ошибку - неопределенный метод `chars '

С использованиемcrunch утиль иbash:

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

Выход:

ab
ba
abc
acb
bac
bca
cab
cba

Учебник здесьhttps://pentestlab.blog/2012/07/12/creating-wordlists-with-crunch/

 ghoti06 мая 2017 г., 07:20
@agc, для любого кода в ответе было бы почти невозможно улучшить код в вопросе. Если OP ищет стратегию для генерации перестановок, то ссылка на то, что делает именно это, кажется хорошим началом.
 agc06 мая 2017 г., 07:27
@ghoti, Re "код в вопросе": в ОП нет никакого кода, только данные: уточните.
 jyz06 мая 2017 г., 00:59
@agc да, ты прав. Я этого не делал, потому что справочные страницы хороши с примерами. Также легко найти, прибегая к помощи. Во всяком случае, я добавил простой со ссылкой на учебник.
 agc06 мая 2017 г., 07:43
@jyz, Добавлен рабочий код, который отвечает на Q. Мы должны удалить эти комментарии.

Более быстрая версия с использованием 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) }

использование:

$ awk -f permute.awk file
 siliconpi05 окт. 2010 г., 11:56
СПАСИБО user131 - я опробую его и посмотрю, как он сравнивается ...

Ваш ответ на вопрос