使用 bash 生成排列 [英] Generating permutations using bash

问题描述

是否可以编写一个 bash 脚本，该脚本可以从文件中读取每一行并为每一行生成排列(不重复)?使用 awk/perl 没问题.

is it possible to write a bash script that can read in each line from a file and generate permutations (without repetition) for each? Using awk / perl is fine.

File
----
ab
abc


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

推荐答案

Pure bash(使用 local，速度更快，但无法击败使用下面的 awk 或下面的 Python 的其他答案):

Pure bash (using local, faster, but can't beat the other answer using awk below, or the Python below):

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(使用子shell，慢得多):

Pure bash (using subshell, much slower):

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

既然提问者提到 Perl 很好，我认为 Python 2.6+/3.X 也很好:

Since asker mentioned Perl is fine, I think Python 2.6+/3.X is fine, too:

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

对于 Python 2.5+/3.X:

For 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('
'.join([''.join(item) for line in open('File') for item in all_perms(line[:-1])]))

在我的计算机上使用更大的测试文件:

On my computer using a bigger test file:

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

这篇关于使用 bash 生成排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！