Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Перестановки чисел

Автор: Litanika 13.5.2006, 16:51

Помогите запрограммировать такую штуку: вводится число классов, в каждом классе число элементов (например числа). Нужно получить строки заданной длины N из всевозможных перестановок этих чисел. Например, 4 класса, в них 2, 2, 1, 1 элементов: [1,1], [2,2], [3], [4], длина строки =3. Должно получиться:
112
113
114
121
122
123
124
131
132
134
141
142
143
211
212
213
214
221
223
232
234
241
242
243
311
312
314
321
322
324
341
342
411
412
413
421
422
423
431
432
Вся проблема в том, что заранее неизвестна длина строки N, и поэтому нельзя сделать просто определенное число вложенных циклов. Помогите пожалуйста!! очень нужно, желательно на Delphi

Автор: SoWa 13.5.2006, 17:25

Просьба простить, код столетней давности, неоптимизированный и вырваный из кода.

Код


procedure cikl(n:integer;s:string);
var i:byte;k:string;
begin
 k:=s;
  if n>1 then
   for i:=1 to 255  do
    begin
       s:=s+chr(i);
       form1.listbox1.items.add(s);
       cikl(n-1,s);
       s:=k;
       form1.label1.Caption:=inttostr(strtoint(form1.label1.Caption)+1);
       SendMessage(form1.ListBox1.Handle, WM_VSCROLL, SB_LINEDOWN, 0);
    end;
end;
...
begin
cikl(2,''); {Если нужна строка длинны 1, то в параметре указывай на единицу больше. Ибо СРУК.}
end;

Код генерирует все строки заданной длинны из 255 символов. Можно заменить массивом символов. На ваше усмотрение.

Автор: Litanika 13.5.2006, 19:41

SoWa
Это не совсем то, что мне нужно, но почти похоже на правду.
Этот способ перебирает ВСЕ сочетания, а у меня количество элементов каждого типа ограничено, например если в твоем примере взять не символы , а цифры, и например будет комбинация 444, то у меня может быть только одна 4. То есть потом придется как-то отсеивать или еще что-то придумывать. А мне нужен алгоритм, чтобы только из существующих элементов сочетания делал.

Добавлено @ 19:52
То есть еще можно так сформулировать: дан массив элементов, сформировать всевозможные сочетания заданной длины и меньше (макс. длина 15 - все сочетания длигой 1, 2, ..., 15), пример массива из предыдущего примера - [1,1,2,2,3,4]

Автор: SoWa 13.5.2006, 20:25

Вот я и говорю- подставляешь вместо s:=s+chr(i); подстановку из массива.

Автор: Litanika 13.5.2006, 23:11

SoWa,
если я правильно поняла, то я делаю массив из элементов (будет arr=[1,1,2,2,3,4]), делаю s:=s+a[i], i пробегает от 1 до length(arr)?
если так сделать, то ничего путного не получается, она мне делает 1, 11, 111 {для первой единицы}, 111, 112, 113, 114, {потом для второй начинает} 11, 111, 111, ...
Так что не получается или что-то я не догоняю?

Автор: SoWa 14.5.2006, 10:58

В общем, этот код даст тебе все перестановки из данного множества. Выбирать повторения придется самой. Это не так сожно. И работу не на много замедлит... Постарайся сама написать выбор повторяющихся элементов и однородных строк типа 222.

Автор: Litanika 14.5.2006, 14:11

SoWa, ок спасибо за помощь, надеюсь щас все получится у меня