☰

Bash 中的排列（ID/令牌的组合）

tag-icon • tag-icon shell-script permutations
Bash 中的排列（ID/令牌的组合）

我不相信这是真正的排列，因为我不希望 ID 的组合以不同的顺序重复。

我有一个包含 1 到 x ID 的列表：

List #1:  1001 1002 1003 1004
List #2:  1002 1004 1005
List #3:  1001 1003 1006
List #4:  1002 1003 1005 1006 1007 1008 1010

ETC。

请记住，列表的长度是可变的，我需要一种方法来获取列表中 ID 的所有可能组合（但不是不同顺序的相同组合）。

例如，列表 #1 将返回：

1001
1002
1003
1004
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
1003 1004
1001 1002 1003
1001 1002 1004
1001 1003 1004
1002 1003 1004
1001 1002 1003 1004

列表 #2 将返回：

1002
1004
1005
1002 1004
1002 1005
1004 1005
1002 1004 1005

我需要在 bash 脚本中工作的解决方案。平心而论，我可以调用Python、PHP等。

任何意见都将受到高度赞赏。

答案1

使用Python：

>>> from itertools import combinations
>>> a = (1001, 1002, 1003, 1004)
>>> [list(combinations(a, i)) for i in range(1, len(a)+1)]
[[(1001,), (1002,), (1003,), (1004,)], [(1001, 1002), (1001, 1003), (1001, 1004), (1002, 1003), (1002, 1004), (1003, 1004)], [(1001, 1002, 1003), (1001, 1002, 1004), (1001, 1003, 1004), (1002, 1003, 1004)], [(1001, 1002, 1003, 1004)]]

要以更好的格式显示它：

>>> print '\n'.join('\n'.join(' '.join(str(i) for i in c) for c in combinations(a, i)) for i in range(1, len(a)+1))
1001
1002
1003
1004
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
1003 1004
1001 1002 1003
1001 1002 1004
1001 1003 1004
1002 1003 1004
1001 1002 1003 1004

从 bash 命令行运行

$ python -c "from itertools import combinations; a=(1001, 1002, 1003, 1004); print '\n'.join('\n'.join(' '.join(str(i) for i in c) for c in combinations(a, i)) for i in range(1, len(a)+1))"
1001
1002
1003
1004
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
1003 1004
1001 1002 1003
1001 1002 1004
1001 1003 1004
1002 1003 1004
1001 1002 1003 1004

作为 shell 函数运行

让我们定义一个 shell 函数：

$ combo() { python -c "import sys, itertools; a=sys.argv[1:]; print '\n'.join('\n'.join(' '.join(str(i) for i in c) for c in itertools.combinations(a, i)) for i in range(1, len(a)+1))" "$@"; }

我们可以按如下方式运行该函数：

$ combo 1001 1002 1003 1004
1001
1002
1003
1004
1001 1002
1001 1003
1001 1004
1002 1003
1002 1004
1003 1004
1001 1002 1003
1001 1002 1004
1001 1003 1004
1002 1003 1004
1001 1002 1003 1004

答案2

和bash：

#! /bin/bash
declare -a list=(1001 1002 1003 1004)

show() {
    local -a results=()
    let idx=$2
    for (( j = 0; j < $1; j++ )); do
        if (( idx % 2 )); then results=("${results[@]}" "${list[$j]}"); fi
        let idx\>\>=1
    done
    echo "${results[@]}"
}

let n=${#list[@]}
for (( i = 1; i < 2**n; i++ )); do
    show $n $i
done

可能不是有史以来最快的实现，但它确实有效：

1001
1002
1001 1002
1003
1001 1003
1002 1003
1001 1002 1003
1004
1001 1004
1002 1004
1001 1002 1004
1003 1004
1001 1003 1004
1002 1003 1004
1001 1002 1003 1004

答案3

另一个 Bash 解决方案，基于 IVlad二元迭代法，还借用了大括号扩展的想法来自赛勒斯和 Malte Skoruppa 的概括：

function binpowerset() (
  list=($@)
  eval binary=( $(for((i=0; i < ${#list[@]}; i++)); do printf '%s' "{0..1}"; done) )
  nonempty=0
  for((power=0; power < ${#binary[*]}; power++))
  do
    binrep=${binary[power]}
    for ((charindex=0; charindex < ${#list[*]}; charindex++))
    do
      if [[ ${binrep:charindex:1} = "1" ]]
      then
         printf "%s " ${list[charindex]}
         nonempty=1
      fi
    done
    [[ $nonempty -eq 1 ]] && printf "\n"
  done
)

像这样称呼它：

$ binpowerset 1001 1003 1006
1006
1003
1003 1006
1001
1001 1006
1001 1003
1001 1003 1006

它根本不节省空间，因为它构建了一个具有 2 N 个元素的二进制表示数组，其中N是集合中元素的数量。它也不节省时间，因为每次调用该函数时它都会构建二进制数组。它全部包装在一个子 shell 中，因此不会污染您的变量名称空间。根据此问题的示例输出，它特别排除“null”或空集。

相关内容