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

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

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

Comments

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

Помоему,Вам сюда,если Вы знаете,что такое компилятор.
(http://www.forum.ishodniki.ru/index.php)

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

http://www.forum.ishodniki.ru/index.php

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

спасибо. что такое компилятор, я знаю) но речь об алгоритме, а не о реализации, с которой проблем нет.)

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

Наверное,ты имеешь в виду формулу?Ведь программа,это и есть алгоритм,способный вывести на экран и ответ твоей задаче :) А так вообще и в ручную можно перебрать

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

да-да. формулу.) все. разобралась. спасибо.

[krimeano.livejournal.com]

много

пусть всего есть 8 букв
для последовательности из одной буквы - 8 вариантов
из двух - 8*7
из трех - 8*7*6
и т. д.
т.е., если есть n букв, из которых составляется слово длины k, получим n!/(n-k)! уникальных слов.
а скока всего, лень считать :(

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

[urod.livejournal.com]

Каждая буква может присутствовать или отсутствовать. Но варианта, когда все буквы отсутствуют, нет. Соответственно, получается 255 последовательностей (2 в восьмой степени минус 1).

void combinations(const char* s) {
int i;
for (i=1; i<256; i++) {
int j=i;
while (j>0) {if (j%2) printf(s[i]); j /= 2;}
printf("\n");
}
}

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

именно так. спасибо)