О великие гуру, помогите плиз.
Задана, напр., коллекция букв или выражений, для простоты скажем — {"A", "B", "C", "D"}. Существует ли алгоритм вывода всевозможных вариантов комбинаций этих букв, без повторов (порядок букв не имеет значения, напр. {A,A} считается повтором {A}, {A,B,C} считается повтором {B,C,A})? Т.е. на выходе должно получаться что-то вроде:
{A}
{B}
{C}
{D}
{A,B}
{A.C} {B,C}
{A,D} {B,D} {C,D}
{A,B,C}
{A,B,D} {B,C,D}
и т.д. (к сожалению, такая упорядоченная структура далее не сохраняется, напр. вылезает дополнительно ACD). Формат вывода конечно же не имеет значения, в итоге оно все в vector<vector<string>> должно идти.
Также буду благодарен за ссылки на что читать/куда смотреть.
Спасибо!
Здравствуйте, Аноним, Вы писали:
А>Задана, напр., коллекция букв или выражений, для простоты скажем — {"A", "B", "C", "D"}. Существует ли алгоритм вывода всевозможных вариантов комбинаций этих букв, без повторов (порядок букв не имеет значения, напр. {A,A} считается повтором {A}, {A,B,C} считается повтором {B,C,A})?
Другими словами, тебе надо сгенерировать множество всех подмножеств данного множества (кроме, возможно, пустого подмножества). Это делается элементарным алгоритмом, идею которого можно записать, например, таким образом: пусть наше исходное множество содержит N элементов (4 в твоем примере). Возьмем N-битное двоичное число (четырехбитное в нашем случае) и каждому элементу исходного множества сопоставим один бит. Затем рассмотрим все эначения этого числа от 1 до 2^N-1 (от 1 до 15 в нашем случае). Для каждого значения будем строить выходное множество, выбирая толко элементы, соответствующие единичным битам. В результате мы получим все, что нам надо.
В твоем примере: пусть четыре бита XXXX соответствуют элементам DCBA. Рассмотрим представления чисел от 1 до 15
1 = 0001 = { A }
2 = 0010 = { B }
3 = 0011 = { A, B }
4 = 0100 = { C }
5 = 0101 = { A, C }
6 = 0110 = { B, C }
7 = 0111 = { A, B, C }
8 = 1000 = { D }
9 = 1001 = { A, D }
10 = 1010 = { B, D }
11 = 1011 = { A, B, D }
12 = 1100 = { C, D }
13 = 1101 = { A, C, D }
14 = 1110 = { B, C, D }
15 = 1111 = { A, B, C, D }
Вот и все. Разумеется, поступать именно так и рассматривать явно биты в двоичных числах совсем не нужно. Можно просто инкрементально конструировать каждое послдующее множество из предыдущего путем добавления к предыдущему и изятия из предыдущего элементов по тому же принципу, по которому меняются биты в последовательных двоичных числах.
Другой вариант алгоритма: наращивать длину генерируемых множеств от коротких к длинным, путем добавления к уже сгенерированным множествам всевозможных элементов, которые "больше" последнего добавленного. Начинаем с длины 1: { A }, { B }, { C }, { D }
Затем будем получать длину 2. К множеству { A } надо по очереди добавить B, С и D: { A, B }, { A, C }, { A, D }
А вот к множеству { B } надо добавить только C и D: { B, C }, { B, D }
К { C } — только D: { C, D }
К { D } ничего добавить нельзя.
С длиной 2 покончено. Переходим к длине 3.
Из { A, B } получается { A, B, C } и { A, B, D }
Из { A, C } — { A, C, D }
Из { A, D } — ничего больше не получается.
Еще из { B, C } мы получим { B, C, D } и на этом все.
И, наконец, длина 4, которая нам из { A, B, C } сделает { A, B, C, D }
Все.
А>>Задана, напр., коллекция букв или выражений, для простоты скажем — {"A", "B", "C", "D"}. Существует ли алгоритм вывода всевозможных вариантов комбинаций этих букв, без повторов (порядок букв не имеет значения, напр. {A,A} считается повтором {A}, {A,B,C} считается повтором {B,C,A})?
АТ>Другими словами, тебе надо сгенерировать множество всех подмножеств данного множества (кроме, возможно, пустого
а еще в таких "красивых" алгоритмах полезно посмотреть, как это делается в коде, и разобраться, почему это работает:
вот C#:
using System;
namespace Subsets
{
class Program
{
static void Main()
{
string elements = "abc";
//string elements = "123456789012345678901234567890123";
ulong maximum = power(elements);
for (ulong i = 0; i < maximum; i++)
{
ulong set = i;
for (int j = 0; j < elements.Length; j++, set >>= 1)
if ((set & 0x01) == 1)
Console.Write(elements[j]);
Console.WriteLine();
}
//Console.ReadLine();
}
private static ulong power(string elements)
{
ulong p = 1;
for (int i = 0; i < elements.Length; i++)
p *= 2;
return p;
}
}
}
зы. реализация у таких красивостей обычно гораздо меньше текстуального описания
я помню, был поражен, когда увидел код решения задачи коммивояжера методом ветвей и границ в 5 строчек, после несколькостраничного описания этого решения...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Здравствуйте, PhantomIvan, Вы писали:
PI>а еще в таких "красивых" алгоритмах полезно посмотреть, как это делается в коде, и разобраться, почему это работает:
PI>вот C#:
PI>PI> private static ulong power(string elements)
PI> {
PI> ulong p = 1;
PI> for (int i = 0; i < elements.Length; i++)
PI> p *= 2;
PI> return p;
PI> }
PI> }
PI>}
PI>
А вот это вот нельзя заменить на 1 << elements.Length ?
_DA>А вот это вот нельзя заменить на 1 << elements.Length ?
согласен
эх, если б кто-то умный просмотрел бы
все мои сорцы...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
PI>>я помню, был поражен, когда увидел код решения задачи коммивояжера методом ветвей и границ в 5 строчек, после несколькостраничного описания этого решения...
LoR>А можно предоставить публике возможность увидеть метод ветвей и границ реализованный в 5 строчек?
ээээ, было это в книге:
Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. — Харьков: Фолио; Ростов н/Д: Феникс, 1997. — 368 с.
то были времена без сканера и пиринговых сетей, поэтому
где ее теперь взять... помню, что была 1 функция на паскале, в 5 строчек
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Здравствуйте, PhantomIvan, Вы писали:
PI>ээээ, было это в книге:
PI>PI>Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. — Харьков: Фолио; Ростов н/Д: Феникс, 1997. — 368 с.
PI>то были времена без сканера и пиринговых сетей, поэтому где ее теперь взять... помню, что была 1 функция на паскале, в 5 строчек
Попробую найти.
Спасибо.
PI>>ээээ, было это в книге:
PI>>PI>>Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. — Харьков: Фолио; Ростов н/Д: Феникс, 1997. — 368 с.
PI>>то были времена без сканера и пиринговых сетей, поэтому где ее теперь взять... помню, что была 1 функция на паскале, в 5 строчек
LoR>Попробую найти.
ну, если не найдешь, я попрошу у кого она точно есть сфоткать ту страничку
(потому что я глядел в инете, не нашел по быстрячку ничего подобного)
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
PI>>ну, если не найдешь, я попрошу у кого она точно есть сфоткать ту страничку
PI>>(потому что я глядел в инете, не нашел по быстрячку ничего подобного)
LoR>Быстрый поиск ничего не дал.
LoR>Предложение о фотосессии принимется.
ага, ну это в течение недели-двух
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
