Bash: Powerset array search

Question

I need a Bash script that will receive an array with n elements as input and return the power circuit of this array.

So for array=(a, b, c, d) output should be

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

Note that no element should repeat (aab, accd, abbc are invalid) and that abc is the same as cba (order is not important).

Each solution to such problems that I found gives either a fixed length (a combination of lengths 2 or 3), or allows you to repeat (for example, aacd) even for other languages ​​(not that I can do much with other languages ​​either ...)

I came up with this:

 string='abcd' 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 

and my conclusion

 a ab abc abcd b bc bcd c cd d 

It lacks some entries, such as ac, ad, abd ...

Any ideas?

Answer 1

This can be done in a straightforward manner, as in any other programming language, interpreting each subset as a binary number, where each bit indicates whether the corresponding element is selected or not. For a set of n- elements, you count from 0 to 2 ⁿ & minus; 1 and take the j -th element in the i -th subset if and only if the jth bit in the binary representation of i is set .

 #! /bin/bash items=(abcd) 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 

Output:

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

Answer 2

It works:

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

Or, more portable:

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

Call it like this (use echo if you want a single line):

 $ echo $(pabcde) 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> 

Note. It works for "complex" element values, just don't use echoes.

 $ p " ab " "-c d-" "gg hh" ab -c d-gg hh -c d-gg hh ab gg hh gg hh ab -c d- -c d- ab 

---

And, a non-recursive option (albeit slower) based on a binary representation of each value. This, however, is basically bash since it makes extensive use of arithmetic expansion.

 #!/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 " $@ " 

Remove the comment character (#) after a='' if you need numbered results.

Answer 3

Assuming your array is a collection of “simple” elements, there is an interesting solution that includes an eval dynamically created curly bracket expression.

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

(It skips the empty line that will be part of each power element, but you can add it manually later.)

Answer 4

building on top of previous answers with eval

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

will provide you

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