Bash: Найти Powerset массива

Question

Мне нужен сценарий Bash, который получит массив с n элементами в качестве входных данных и вернет силовую схему этого массива.

Так array=(a, b, c, d) выход должен быть

a 
ab 
abc 
abcd 
abd 
ac 
acd 
b 
bc 
bcd 
c 
cd 
d 

Обратите вниманием, что ни один элемент не должен повторяться (ааЪ, АПЗ, Абы не действительны), и что а такие же, как CBA (порядок не важен).

Каждое решение для подобных проблем, которое я нашел, дает либо фиксированную длину (комбинацию длины 2 или 3), либо позволяет повторять (например, aacd) даже для других языков (не то, что я могу многое сделать с другими языками ...)

Я пришел с этим:

string='a b c d' 
read -a array <<< "$string" 
count="${#array[@]}" 
level=0 
for ((level = 0; level < $count; level++)); do 
    for ((i = $level; i < $count; i++)); do 
    output+=" ${array[$i]}" 
    echo $output 
    done 
output='' 
done 

и мой выход

a 
a b 
a b c 
a b c d 
b 
b c 
b c d 
c 
c d 
d 

это отсутствуют некоторые элементы, такие как AC, AD, абд ...

Любые идеи?

Answer 1

Это можно сделать прямолинейно, как на любом другом языке программирования, интерпретируя каждое подмножество как двоичное число, где каждый бит указывает, выбран ли соответствующий элемент или нет. Для п элементного множества, то отсчет от 0 до 2 ^н   − 1 и принять ямайских его элемента в -й подмножество я тогда и только тогда, когда J -х бит в двоичном представлении i.

#! /bin/bash 

items=(a b c d) 
n=${#items[@]} 
powersize=$((1 << $n)) 

i=0 
while [ $i -lt $powersize ] 
do 
    subset=() 
    j=0 
    while [ $j -lt $n ] 
    do 
     if [ $(((1 << $j) & $i)) -gt 0 ] 
     then 
      subset+=("${items[$j]}") 
     fi 
     j=$(($j + 1)) 
    done 
    echo "'${subset[@]}'" 
    i=$(($i + 1)) 
done 

Выход:

'' 
'a' 
'b' 
'a b' 
'c' 
'a c' 
'b c' 
'a b c' 
'd' 
'a d' 
'b d' 
'a b d' 
'c d' 
'a c d' 
'b c d' 
'a b c d' 

Answer 2

Если предположить, что массив представляет собой набор из «простых» элементов, есть интересное решение с eval ИНГАМИ динамически генерируемое выражением скобки.

$ array=(a b c d) 
$ printf -v br "{%s,}" "${array[@]}" 
$ echo $br 
{a,}{b,}{c,}{d,} 
$ eval "printf '%s\\n' $br" 

(Он опускает пустую строку, которая была бы частью каждого Powerset, но вы можете добавить, что впоследствии вручную.)

Answer 3

Это работает:

$ p(){ eval echo $(printf "{%s,}" "$@"); } 
$ p a b c d 
abcd abc abd ab acd ac ad a bcd bc bd b cd c d 

Или, более портативный:

p() { 
     [ $# -eq 0 ] && { echo; return; } 
     (shift; p "$@") | while read a ; do printf '%b' "$1$a\n$a\n"; done 
} 
p "$@" 

Вызов как это (использование эхо, если вы хотите одну строку):

$ echo $(p a b c d e) 
abcde bcde acde cde abde bde ade de abce bce ace ce abe be ae e abcd bcd acd cd abd bd ad d abc bc ac c ab b a<br> 

Примечание: оно работает для «сложных» значений элементов, просто не используйте эхо.

$ p " a b " "-c d-" "gg hh" 
a b -c d-gg hh 
-c d-gg hh 
a b gg hh 
gg hh 
a b -c d- 
-c d- 
a b 

---

И, не-рекурсивный вариант (хотя и медленнее), основанный в двоичном представлении каждого значения. Это, однако, в основном bash, поскольку он широко использует Арифметическое расширение.

#!/bin/bash 

powerset(){ 
[[ $# -eq 0 ]] && { echo "Missing set of arguments" >&2; exit 2; } 
local n ns; ((n=$#, ns=1<<n)) 

for ((i=1; i<ns ; i++)); do 
    a=''; # printf "%4.4s " "$i" 
    for ((j=1; j<=n; j++)); do 
    ((i & 1<<(j-1))) && a="${a}""${!j}" ; 
    done 
    echo "$a" 
done 
} 

powerset "$@" 

Удалить символ комментария (#) после a='', если вам нужно пронумерованных результаты.

Answer 4

здание на вершине предыдущих ответов с Eval

eval echo $(sed 's/./{&,}/g' <<< "abcd") | tr ' ' '\n' | sort 

даст вам

a 
ab 
abc 
abcd 
abd 
ac 
acd 
ad 
b 
bc 
bcd 
bd 
c 
cd 
d