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

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

Без доп. либ.

itertools - часть яп

У меня не питон.

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

Использовать скриптовые яп для тестирования - вполне.

Вы с первого раза не понимаете?

Это?

Вроде нет. У меня длина переменная и нулей нет.

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

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

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

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

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

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

Пример кода на 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]

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

#!/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)]).

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

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

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

from itertools import combinations?

На Перле:

[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++;
}

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

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

Беру свои слова назад, ибо к счастью в расте тоже есть 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...

С матаном на вы, увы.

Ты во мне души не чаешь?

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

Первый ответ в теме был.

Где? Там не то.

001 -> 3

010 -> 2

011 -> 2 3

100 -> 1

101 -> 1 3

110 -> 1 2

111 -> 1 2 3

Рили такой тупой что ли?

Зарегься, чтобы я мог тебя игнорить.

такие они писаки на расте)

а где тут матан? 11 класс школы введение в комбинаторику, а не расчет интеграла Лебега.

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)

Для меня - матан.

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> 

all = 2**len(words) - 1

fix

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

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

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)))

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

Матан - это, в том числе, и сленг.

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

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

zOMG. Я бы просто Data.List.subsequences дёрнул.

А как тогда понтоваться манадной магией?

man одометр

Это тут при чём?

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

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

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

Она не актуальна, у тебя всё равно предикат завязан на списки.

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

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

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

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

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

Нет.

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

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