Извлечь все возможные упорядоченные подмножества
У меня есть набор элементов, из которых я хочу извлечь ordered подмножества. Что я имею в виду под ordered Подмножеством является то, что я не могу переключать элементы внутри набора. Я привел три примера, чтобы показать, как я пытаюсь решить проблему.
- Как я могу извлечь эти подмножества рекурсивно?
- Вы имеете в виду псевдокод?
- {. } = подмножество
Пример 1
Позволять S = {f1,f2,f3} быть набором из 3 элементы. Я хочу извлечь все возможные упорядоченные подмножества следующим образом:
-{f1},{f2},{f3} // {f1} is a subset, {f2} is a subset etc.
-{f1,f2},{f3} // {f1,f2} form a subset and {f3} is also a subset
-{f1},{f2,f3} // {f1} is a subset and {f2,f3} form a subset
Пример 2
Позволять S = {f1,f2,f3,f4} быть составленным из 4 элементы.
Возможные упорядоченные подмножества:
-{f1},{f2},{f3},{f4}
-{f1,f2},{f3,f4}
-{f1},{f2,f3},{f4}
-{f1},{f2},{f3,f4}
-{f1,f2,f3}{f4}
-{f1},{f2,f3,f4}
-{f1,f2},{f3},{f4}
-{f1,f2,f3,f4}
Пример 3
Позволять S = {f1,f2,f3,f4,f5} быть составленным из 5 элементы.
Возможные упорядоченные подмножества:
-{f1},{f2},{f3},{f4},{f5}
-{f1,f2},{f3},{f4},{f5}
-{f1},{f2,f3},{f4},{f5}
-{f1},{f2},{f3,f4},{f5}
-{f1},{f2},{f3},{f4,f5}
-{f1,f2},{f3,f4},{f5}
-{f1},{f2,f3},{f4,f5}
-{f1,f2,f3},{f4,f5}
-{f1,f2,f3},{f4},{f5}
-{f1},{f2,f3,f4},{f5}
-{f1},{f2},{f3,f4,f5}
-{f1,f2},{f3,f4,f5}
-{f1,f2,f3,f4}{f5}
-{f1},{f2,f3,f4,f5}
- etc...
Решение
Если массив содержит набор, измените массив так, чтобы между каждым элементом был один пробел. Это пространство зарезервировано для разбиения. Примите любое соглашение об именах. 0 подразумевает отсутствие раздела, тогда как 1 подразумевает раздел. Теперь пройдемся по массиву, чтобы рекурсивно добавить 1 или же 0 в разделе. Все возможные комбинации могут быть сгенерированы.
принятие Пример 1:
S = {f1,f2,f3}
S'= {f1,0,f2,0,f3}
Таким образом, подмножества будут:
{f1,0,f2,0,f3}, {f1,0,f2,1,f3}, {f1,1,f2,0,f3}, {f1,1,f2,1,f3}
который такой же как:
{f1,f2,f3}, {{f1,f2},{f3}}, {{f1},{f2,f3}}, {{f1},{f2},{f3}}
Если вы не хотите, чтобы исходный набор появлялся в наборе всех подмножеств, просто не учитывайте состояние, в котором содержится каждый раздел 0,
Другие решения
Допустим, множество S = {a, b, c, d} содержит 4 элемента. Все подмножества могут быть сгенерированы записью 2 ^ n — 1 в двоичном виде и последующим вычитанием.
а б в г
1 1 1 1 => (a b c d)
1 1 1 0 => (a b c) (d)
1 1 0 1 => (a b d) (c) // Логика состоит в том, чтобы объединить все 1 вместе
1 1 0 0 => (a b) теперь 0 0 можно далее разбить на (1 1) => (c d), (1 0) => (c) (d)
1 0 1 1 => (a c d) (b)
1 0 1 0 => (a c) теперь 0 0 можно далее разбить на (1 1) => (b d), (1 0) => (b) (d)
1 0 0 1 => (a d) те же шаги, что и выше
1 0 0 0 => (a) теперь осталось с 3 нулями, мы имеем b c d как 3 комплекта, теперь мы можем начать заново с 1 1 1, а затем перейти к 1 1 0 и так далее.
Таким образом, мы можем генерировать все подмножества.