LINUX.ORG.RU

Ищу алгоритм генерации всех сочетаний элементов списка

 ,


1

2

Есть список длиной n. Нужно получить список списков всех возможных сочетаний длиной от 1 до n без повторов и в любой последовательности.

Не уверен, что это верный термин, но лучше ничего не нагуглилось.

Пример, чтобы было всем понятно:

1 2 3

1
2
3
1 2
1 3
2 3
1 2 3

Если код будет выдать, к примеру, 3 2, а не 2 3 - не страшно. Мне порядок не важен.

Видимо не по тому слову гуглю, ибо выдаёт только примеры перестановки в списке фиксированной длины. Типа «список сочетаний из 4-х цифр». Но мне это не нужно.

Я конечно слепил костыль, но мне кажется, что есть готовый алгоритм для данной задачи.

PS: нет, это не лаба, и не тестовое задание. Я пытаюсь написать тест для проги, который будет перебирать все возможные аргументы CLI.

Перебирай все числа от нуля до 2^n-1 и бери списки номеров установленных битов.

TeopeTuK ★★★★ ()
Последнее исправление: TeopeTuK (всего исправлений: 1)
import itertools
i = 1
stuff = [x for x in xrange(1, 100)]
for L in range(0, len(stuff)+1):
  for subset in itertools.combinations(stuff, L):
    i += 1
    # if subset: print(subset)
print 'all %d' % i
bryak ★★★★ ()

Есть. Называется двоичная система счисления.

a1batross ★★★★★ ()

По-моему для сочетаний будет очень похожий алгоритм, что и для перестановок. Только нужно работать со множеством, а не со списком. Сначала возвращаем само множество. Потом либо исключаем первый (минимальный) элемент, либо оставляем. Получили разбиение. Значит, нужно хранить еще множество, которое будет добавляться к результату. В этом дополнительном множестве будут просмотренные элементы, одобренные для включения. Затем рекурсивно заходим для обеих ветвей разбиения. Примерно так

dave ★★★★★ ()
Ответ на: комментарий от dave

Тогда вот это дополнительное множество и возвращать на каждом шаге, пропуская (или нет) начальное пустое.

dave ★★★★★ ()

Пример кода на R:

subsets <- function(N) {
    for (n in 1:2^N-1) {
	x <- 1:N
	print(x[bitwAnd(2^(x-1), n)>0])
    }
}
subsets(5)

TeopeTuK ★★★★ ()

Программист не может ни в комбинаторику, ни даже в stack overflow. Хост, масло, лор.

Зато на расте пишет.

anonymous ()

Пример кода на Tcl. Причем тут два вложенных цикл, поэтому код легко переписать на любой императивный язык.

proc subsets {N} {
    set res {}
    for {set i 0} {$i < 2**$N} {incr i} {
	set current {}
	for {set j 1} {$j <= $N} {incr j} {
	    if {2**($j-1) & $i} {
		lappend current $j
	    }
	}
	lappend res $current
    }
    return $res
}
puts [subsets 5]

TeopeTuK ★★★★ ()

Пример с рекурсией.

#!/usr/bin/escript

subsets(N) ->
    subsets([], N, (1 bsl N) - 1).

subsets(Acc, _N, 0) ->
    [[] | Acc];
subsets(Acc, N, K) ->
    subsets([lists:filter(fun(L) ->
			    if (1 bsl (L-1)) band K > 0 -> true;
			       true -> false
			    end
			  end, lists:seq(1, N)) | Acc], N, K-1).

main(_) ->
    io:format("~p~n", [subsets(5)]).

TeopeTuK ★★★★ ()
[xxxxx ~]$ cat a.php
<?php
$n = 3;
$maxCount = 2 ** $n;
for ($i = 1; $i < $maxCount; $i++) {
    $variation = $i;
    $list = [];
    for ($j = 0; $j < $n; $j++) {
        $shouldShow = $variation % 2;
        if ($shouldShow) {
            $list[] = $j + 1;
        }
        $variation = $variation / 2;
    }
    echo implode(', ', $list) . "\n";
}

[xxxxx ~]$ php a.php
1
2
1, 2
3
1, 3
2, 3
1, 2, 3
[xxxxx ~]$
PHPFan ()

Тебе нужно просто множество всех подмножеств за вычетом одного пустого множества: 2^A \ {ø}

Deleted ()

Ключевое слово — powerset. Ну и раз уж тут меряются реализациями на php:

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])
nezamudich ★★ ()
Ответ на: комментарий от PHPFan

На Перле:

[xxxxx ~]$ cat b.pl
use strict;

my $maxLength = 3;
my $permutationsCount = 2 ** $maxLength;

my $currentPermutationNr = 1;
while ($currentPermutationNr < $permutationsCount) {
    my $data = $currentPermutationNr;
    my $currNumber = 1;
    my @list = ();
    while ($data) {
        push @list, $currNumber if $data % 2;
        $data /= 2;
        $currNumber++;
    }
    print join(', ', @list), "\n";
    $currentPermutationNr++;
}
PHPFan ()

Лол. Столько вариантов, но я ни разу не указывал язык.

Мне-то псевдокод нужен, а не фичи языка.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от bryak

Беру свои слова назад, ибо к счастью в расте тоже есть itertools.

let list = vec!['a', 'b', 'c', 'd'];
for i in 0..list.len() {
    for n in list.iter().combinations(i + 1) {
        println!("{:?}", n);
    }
}

То есть задача решена. Да и сам алгоритм уже подсмотрел в: https://github.com/bluss/rust-itertools/blob/954df1e5201e3b0544ab965be99a4a4b...

RazrFalcon ★★★★★ ()
Ответ на: комментарий от bryak

product луче:

from itertools import cycle, product

words = 'мама мыла раму'.split()

for p in product(*zip(cycle(['']), words)):
    if any(p): 
        print(' '.join(filter(None, p)))
раму
мыла
мыла раму
мама
мама раму
мама мыла
мама мыла раму

all = 2**len(words)

anonymous ()

Pure CL:

(defun combination-list (elements)
  (let ((result-list (list)))
    (labels (($iter-combination (comb list)
               (if list
                   (destructuring-bind (fel &rest rel)
                       list 
                     ($iter-combination (cons fel comb)
                                        rel)
                     ($iter-combination comb rel))
                   (push comb result-list))))
      ($iter-combination (list)
                         elements))
    ;; NIL is the first element always
    (rest result-list)))

CL-USER> (combination-list (reverse '(a b c d f)))
((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) (F) (A F) (B F) (A B F) (C F) (A C F) (B C F) (A B C F)
 (D F) (A D F) (B D F) (A B D F) (C D F) (A C D F) (B C D F) (A B C D F))
CL-USER> 
anonymous ()
Ответ на: комментарий от anonymous

нет, у того комментатора считаются все варианты, причём они ещё прибавляются зачем-то к единице, так что я поправил, а ты чё, такой умный что ли? ))

anonymous ()
Ответ на: комментарий от RazrFalcon

Матан это сокращение от «математический анализ», а не «неведомая мне хренотень». И то обычно под анализом имеется в виду простейший calculus, а не, скажем, global analysis.

mix_mix ★★★★★ ()
Ответ на: комментарий от anonymous

Pure CL, нерекурсивная версия:

(defun combination-list (elements)
  (loop :for i :downfrom (1- (ash 1 (length elements)))
          :to 1
        :collect (loop :for el :in elements
                       :for j :upfrom 0
                       :when (logbitp j i)
                         :collect el)))
anonymous ()
Ответ на: комментарий от mix_mix

«Calculus» – по-латински значит «счёт». Бессмысленное, декоративное слово. «Анализ» намного лучше.

Deleted ()
Ответ на: комментарий от Deleted

«Calculus» – по-латински значит «счёт». Бессмысленное, декоративное слово. «Анализ» намного лучше.

ну на русский традиционно мне кажется переводить как «исчисление»: lambda calculus - лябмда исчисление, «как там на ихнем бесконечно-малые» калькулюс - исчисление бесконечно малых, и так далее.

AndreyKl ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Все перестановки можно получить по принципу работы одометра.
123
124
125
...
129
130
132

J ★★★★ ()

Есть список длиной n

Ты упустил самый важный момент - есть ли в списке одинаковые элементы и что значит «без повторов» - без повторов элементов, или индексов.

no-such-file ★★★★★ ()

пц. тебе же написали

какой-нибудь big_int длиной в n бит возьми и от единицы до нуля(он переполнится) его увеличивай на 1.

биты = 1 это выбраный элемент.

чо, опять С++ не даёт головой думать?

ckotinko ☆☆☆ ()
Ответ на: комментарий от no-such-file

есть ли в списке одинаковые элементы

Нет.

без повторов элементов, или индексов

В чём разница?

RazrFalcon ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.