Версия для печати темы

Автор: Unconnected 23.11.2009 17:29

Привет всем.

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

Искал по форуму, но нашел только теоретическую часть.

Автор: volvo 23.11.2009 17:56

Значит, плохо искал. FAQ -> http://forum.pascal.net.ru/index.php?s=&showtopic=3777&view=findpost&p=52823 , подмножества - твой случай.

Автор: Unconnected 23.11.2009 18:42

А там с повторениями генерируется?

Просто у меня задание, нужно найти количество способов, которыми можно из цифр 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 23.11.2009 18:46

А запустить и посмотреть?

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 23.11.2009 18:49

Если тут код нельзя постить, прошу перенести в нужный раздел:)

Автор: volvo 23.11.2009 20:14

А тебе обязательно считать вручную? Вот это: http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%B5%D0%BB)#.D0.9A.D0.BE.D0.BB.D0.B8.D1.87.D0.B5.D1.81.D1.82.D0.B2.D0.BE_.D0.BA.D0.BE.D0.BC.D0.BF.D0.BE.D0.B7.D0.B8.D1.86.D0.B8.D0.B9 не поможет? Или у тебя могут быть разные числа, не только по порядку 1 .. n?

Кстати, тоже может оказаться полезным... Разбиения (а не композицию) я делал вот тут: http://forum.pascal.net.ru/index.php?s=&showtopic=6327&view=findpost&p=47388 , если теперь каждое из разбиений проверить на возможность перестановки внутри него элементов - то будет то, что тебе нужно.