Помощь - Поиск - Пользователи - Календарь
Полная версия: Нахождение всех возможных строк
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
Unconnected
Привет всем.

Подскажите пожалуйста алгоритм нахождения всех возможных строк из заданной.
Например, дана строка 123456, варианты могут быть любой длины, которая <=6. Если можно, куском кода..

Искал по форуму, но нашел только теоретическую часть.
volvo
Цитата(Unconnected @ 23.11.2009 12:29) *
Искал по форуму, но нашел только теоретическую часть.
Значит, плохо искал. FAQ -> Комбинаторика , подмножества - твой случай.
Unconnected
А там с повторениями генерируется?

Просто у меня задание, нужно найти количество способов, которыми можно из цифр 1 2 3 4 5 6 получить число K (в сумме, в смысле). Я немного дополнил код volvo:

var
f:textfile;
n,i2,i,k,h,j,sc:integer;
a:array[1..100] of byte;
begin
assignfile(f,'input.txt');
reset(f);
read(f,k);
closefile(f);
fillchar(a, sizeof(a), 0);
n:=6;
sc:=0;
for i:=1 to n do a[i]:=i;
repeat
if (a[1]=k)or(a[1]+a[2]=k)or(a[1]+a[2]+a[3]=k)or(a[1]+a[2]+a[3]+a[4]=k)or(a[1]+a[2]
+a[3]+a[4]+a[5]=k)
or(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]=k) then inc(sc);
i:=n;
while a[i-1]>a[i] do dec(i);
j:=i-1;
h:=a[j];
while a[i+1]>h do inc(i);
a[j]:=a[i]; a[i]:=h;
i:=j+1; k:=n;
while i<k do begin
h:=a[i]; a[i]:=a[k]; a[k]:=h;
inc(i); dec(k)
end
until j=0;


Переменная sc - собственно, счётчик способов. Только на k=4 он вместо 8 выдаёт невероятную сумму..
volvo
А запустить и посмотреть?
Running "__subset.exe"
3
0 0 0 0 0 0
0 0 1 0 0 1 3
0 1 0 0 1 1 2 3
0 1 1 0 1 0 2
1 0 0 1 1 0 1 2
1 0 1 1 1 1 1 2 3
1 1 0 1 0 1 1 3
1 1 1 1 0 0 1

Unconnected
Если тут код нельзя постить, прошу перенести в нужный раздел:)
volvo
А тебе обязательно считать вручную? Вот это: http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%....86.D0.B8.D0.B9 не поможет? Или у тебя могут быть разные числа, не только по порядку 1 .. n?

Кстати, тоже может оказаться полезным... Разбиения (а не композицию) я делал вот тут: разложение числа , если теперь каждое из разбиений проверить на возможность перестановки внутри него элементов - то будет то, что тебе нужно.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.