击：查找数组的Powerset [英] Bash: Finding Powerset of array

问题描述

我需要一个bash脚本，会得到与n个元素作为输入数组并返回该数组的幂。

I need a Bash script that will get an array with n elements as input and return the powerset of that array.

因此​​，对于 =阵列（A，B，C，D）输出应为

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

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

请注意，任何元件应重复（AAB，ACCD，ABBC无效），并且ABC是一样CBA（顺序并不重要）。

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

每一个解决类似的问题，我发现给一个固定长度（长度为2的组合或3），或者允许重复（如AACD），甚至对其他语言（不，我可以做的与其他语言要么...）

Every solution to similar problems I found gives either a fixed length (combination of length 2 or 3) or allows repetition (like aacd), even for other languages (not that I can do much with other languages either...)

我想出了这一点：

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某些条目，ABD ......

It's missing some entries like ac, ad, abd...

任何想法？

推荐答案

它可以其中每一位指示是否相应做直向前正如由间preting每个子集将用作二进制数的任何其它程序设计语言元件选择与否。对于 N 的-element集，从0到2计数 ^名词 ＆NBSP;＆减1，并采取Ĵ -th项目到我 -th子集，当且仅当Ĵ中的二进制重新presentation -th位我设置。

It can be done straight-forwardly just as in any other programming language by interpreting each subset as a binary number where each bit indicates whether the respective element is chosen or not. For an n-element set, you count from 0 to 2ⁿ −1 and take the j-th item into the i-th subset if and only if the j-th bit in the binary representation of i is set.

#! /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'

这篇关于击：查找数组的Powerset的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！