комбинаторика

[http://users.livejournal.com/__le__/]

Не могу сориентироваться...
Есть 8 букв (допустим, abcdefgh). Как найти все возможные комбинации, полученные из этих букв? При этом важно сохранять порядок следования (т.е., может быть adef, но не faс). Количество символов в сочетаниях - от 1 до 8, буквы не повторяются.
Если можно, дайте ссылку на литературу или он-лайн программы...
В идеале, конечно, найти какой-то способ получить список всех этих комбинаций, а не только количество.
Или подскажите, пожалуйста - может быть, есть специализированные сообщества.
спасибо.

Comments

[akeepaki.livejournal.com]

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

Суть в следующем, у нас есть слово из восьми букв "abcdefgh", которое мы представляем как s:=m[a]+m[b]+m[c]+m[d]+m[e]+m[f]+m[g]+m[h]. Мы прогоняем все возможные варианты расположения букв. И если индексы букв удовлетворяют нашим условиям (то есть каждая следующая буква старше предыдущей и не равна ей) то записываем эту комбинацию в файл.

сам условный код (нету открытия файла, закрытия и т.д., но алгоритм, должен быть ясен):

var
A,B,C,D,E,F,G: integer;
M[1..8] of char; //забыл как правильно массивы объявлять :)
file_out: file of text; //текстовый файл, куда записываются все подходящие комбинации


begin
M[1]:='a';
M[2]:='b';
M[3]:='c';
M[4]:='d';
M[5]:='e';
M[6]:='f';
M[7]:='g';
M[8]:='h';

for a:=1 to 8 do
begin
for b:=1 to 8 do
begin
for c:=1 to 8 do
begin
for d:=1 to 8 do
begin
for e:=1 to 8 do
begin
for f:=1 to 8 do
begin
for g:=1 to 8 do
begin
for h:=1 to 8 do
begin

if (H>G) and (H>F) and (H>E) and (H>D) and (H>C) and (H>B) and (H>A)
and (G>F) and (G>E) and (G>D) and (G>C) and (G>B) and (G>A)
and (F>E) and (F>D) and (F>C) and (F>B) and (F>A)
and (E>D) and (E>C) and (E>B) and (E>A)
and (D>C) and (D>B) and (D>A)
and (C>B) and (C>A)
and (B>A) then writeln(file_out, M[A]+M[B]+M[C]+M[D]+M[E]+M[F]+M[G]+M[H])

if (G>F) and (G>E) and (G>D) and (G>C) and (G>B) and (G>A)
and (F>E) and (F>D) and (F>C) and (F>B) and (F>A)
and (E>D) and (E>C) and (E>B) and (E>A)
and (D>C) and (D>B) and (D>A)
and (C>B) and (C>A)
and (B>A) then writeln(file_out, M[A]+M[B]+M[C]+M[D]+M[E]+M[F]+M[G])

if (F>E) and (F>D) and (F>C) and (F>B) and (F>A)
and (E>D) and (E>C) and (E>B) and (E>A)
and (D>C) and (D>B) and (D>A)
and (C>B) and (C>A)
and (B>A) then writeln(file_out, M[A]+M[B]+M[C]+M[D]+M[E]+M[F])

if (E>D) and (E>C) and (E>B) and (E>A)
and (D>C) and (D>B) and (D>A)
and (C>B) and (C>A)
and (B>A) then writeln(file_out, M[A]+M[B]+M[C]+M[D]+M[E])

if (D>C) and (D>B) and (D>A)
and (C>B) and (C>A)
and (B>A) then writeln(file_out, M[A]+M[B]+M[C]+M[D])

if (C>B) and (C>A)
and (B>A) then writeln(file_out, M[A]+M[B]+M[C])

if (B>A) then writeln(file_out, M[A]+M[B])
end;
end;
end;
end;
end;
end;
end;
end;

[akeepaki.livejournal.com]

Сам уже заметил два косяка, забыл сделать для одного символа. (для этого достаточно вставить перед началом восьми ендов writeln(file_out, M[A]), и еще в таком сочетании будут писаться повторы правильных комбинаций. Для этого можно запустить еще один цикл. Он записывает первую строку из файла, сравнивает ее со всеми последующими, если нет повтора - записывает в новый файл, и так далее, получим в новом файле только уникальные значения, без повторяющихся =).

[http://users.livejournal.com/__le__/]

спасибо за идею алгоритма!)сейчас попробую написать на перле. думаю, должно получиться)

[akeepaki.livejournal.com]

Всегда рад помочь :). Сработать вроде должно на самом деле. (главное без опечаток все написать =). и всунь счетчик, интересно на самом деле, сколько же их :).

[http://users.livejournal.com/__le__/]

все действительно работает. 255 :)