☰

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

など。

リストの長さは可変であることを念頭に置いて、リストから可能なすべての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

シェル関数として実行

シェル関数を定義しましょう。

$ 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

IVladに基づく別のBashソリューションバイナリ反復方法、また借りキャリブレータ拡張のアイデアサイラスとマルテ・スコルパから一般化する:

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セットの要素数です。また、関数が呼び出されるたびにバイナリ配列を構築するため、時間が節約されません。変数の名前空間を汚染しないように、すべてがサブシェルに包まれています。この質問の出力例によると、「null」または空のセットは具体的に除外されます。

関連情報