Кажется, что проблема действительно заключается в создании множества возможных подмножеств данного набора. который иногда называют powerset набора.
В основном есть 3 возможных решения:
1) Биномиальные коэффициенты. Смотри http://en.wikipedia.org/wiki/Binomial_coefficient
Реализация может быть найдена в itertools Pyton. Биномиальные коэффициенты дают вам подмножества определенной длины. Если вы объедините подмножества от длины 0 до длины вашего исходного набора, все готово.
2) Рекурсивный алгоритм, который "выращивает" подмножества в поколениях. Смотрите ответ Киото. См. Мою более подробную версию ниже. В статье в Википедии упоминается треугольник Паскаля, который является подсказкой для такого алгоритма
3) Элемент находится в подмножестве или нет. Это означает, что есть 2 ^ (длина набора) подмножеств.
Каждое подмножество может быть закодировано как двоичное число с длиной цифр подмножеств.
это сделано в ответе NT3RP. Вы также можете использовать массив логических значений для этого вместо строки. Я публикую свою версию C # ниже.
Моя рекурсивная версия Powerset в coffeescript, основанная на реализации в Miranda.
(Мне было интересно, смогу ли я написать его в Coffeescript так же компактно, как в Miranda, и тогда я нашел этот вопрос)
powerset в Миранде
powerset [] = [[]]
powerset (x:xs) = [[x] ++ y | y <- ys] ++ ys
where ys = powerset xs
powerset в coffeescript:
powerset = (zs) ->
if zs.length is 0
[[]]
else
[x,xs...]=zs
ys=powerset xs
result=([x].concat y for y in ys).concat ys
# number of elements in powerset is 2^length of the powerset
res=powerset [1,2,3,4,5,6,7,8,9,10]
console.log res
console.log "length:" +res.length
Мои интересы во всем этом:
Я написал C # реализацию подхода двоичных чисел для генерации
подмножества некоторое время назад. Ради интереса я также хотел написать версию, которая "увеличивает" подмножества.
Я знал Миранду очень лаконичным языком функционального программирования. Я задавался вопросом, допускает ли coffeescript тот же уровень, что и succinctnes. Я не смог достичь этого в Scala, F # или Clojure. Я не смог сделать это в coffeescript, но «Киото» показал, как это делается.
Ниже версии C # как IEnumerable. Он генерирует кортежи элементов, которые находятся в подмножестве, и все остальные элементы.
...
//imports and house keeping removed
private static IEnumerable<Tuple<IList<T>,IList<T>>> SubsetImpl<T>(this IList<T> argList){
int elementCount=argList.Count;
int bits=(1<<elementCount);//2 to the power of elementCount
List<Tuple<IList<T>,IList<T>>> subsets=new List<Tuple<IList<T>, IList<T>>>(bits);
for(int i=0;i<bits;i++){
int[] mask={i};
BitArray flags=new BitArray(mask);
IList<T> incomb=new List<T>();
IList<T> outcomb=new List<T>();
for(int j=0;j<argList.Count;j++){
if( flags[j]){
incomb.Add(argList[j]);
}else{
outcomb.Add(argList[j]);
}
}
Tuple<IList<T>,IList<T>> t=new Tuple<IList<T>,IList<T>>(incomb,outcomb);
subsets.Add(t);
}
return subsets;
}
...