Permutações no Bash (Combinações de IDs / Tokens)

Question

Eu não acredito que isso seja uma permutação verdadeira, já que eu não quero uma combinação de IDs duplicados em uma ordem diferente.

Eu tenho uma lista de 1 a x IDs:

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.

Tendo em mente que as listas são variáveis em comprimento, eu preciso de uma maneira de obter todas as combinações possíveis dos IDs em uma lista (mas não da mesma combinação em uma ordem diferente).

Por exemplo, a lista nº 1 retornaria:

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

A lista # 2 retornaria:

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

Eu preciso da solução para trabalhar em um script bash. Com toda a justiça, eu poderia chamar Python, PHP, etc.

Qualquer entrada é muito apreciada.

    

Answer 1

Usando 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)]]

Para exibir isso em um formato melhor:

>>> 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

Executando a partir de uma linha de comando 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

Executando como uma função de shell

Vamos definir uma função de 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))" "$@"; }

Podemos executar a função da seguinte forma:

$ 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

    

Answer 2

com 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

Provavelmente não é a implementação mais rápida de todas, mas funciona:

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

    

Answer 3

No entanto, outra solução de Bash, baseada no método de iteração binária do IVlad, também empresta o idéia de expansão de abraço de Cyrus com Malte Skoruppa's generalização :

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
)

Chame assim:

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

Não é nada eficiente em termos de espaço, pois ele cria um array de representação binária que possui 2 elementos ^N , em que N é o número de elementos no conjunto. Também não é eficiente em termos de tempo, pois constrói esse array binário toda vez que você chama a função. Está tudo embrulhado em um sub-shell, então ele não irá poluir seu namespace variável. Exclui especificamente o conjunto "nulo" ou vazio, de acordo com a saída da amostra deste Questionário.