Получить все возможные подмножества - сохранение порядка

Question

Это продолжение этого вопроса: Генерация всех "уникальных" подмножеств набора (не powerset)

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

Пример:

[1, 2, 3]

Результат:

[[1], [2], [3]]
[[1, 2], [3]]
[[1], [2, 3]]
[[1, 2, 3]]

Answer 1

Если я правильно понимаю, вы хотите вставить «разделители» в список, чтобы разделить его.Принимая ваш пример и используя символ | для обозначения разделителя,

1 2 3
1 2|3
1|2 3
1|2|3

- это решения, которые вы хотите.

В списке (я называю это списком, а ненабор, потому что вам нужен сохраненный порядок) из n элементов, есть n-1 потенциальных позиций для разделителя.В приведенном выше примере есть две позиции.В каждой позиции разделитель может присутствовать или отсутствовать.

Вы можете использовать двоичное представление чисел от 0 до 2^(n-1) - 1, чтобы перечислить все возможные расположения разделителей.В вашем примере это будет число от 0..3.

0:  00
1:  01
2:  10
3:  11

Answer 2

Я уже ответил на этот вопрос для Python , поэтому я быстро перенес свое решение на Ruby:

def spannings(lst)
  return enum_for(:spannings, lst) unless block_given?

  yield [lst]
  (1...lst.size).each do |i|
    spannings(lst[i..-1]) do |rest|
      yield [lst[0,i]] + rest
    end
  end
end

p spannings([1,2,3,4]).to_a

Смотрите мой другой ответ для полного объяснения того, как и почемуэто работает.