ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм
31 сообщений из 31, показаны все 2 страниц
  все  
алгоритм
    #38689287
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Не могу придумать, как оптимально сделать следующий алгоритм:
Входные данные:
некоторый массив чисел: 1, 2, ..., N
некоторый массив массивов, содержащих произвольные списки этих чисел: { {1}, {1,2,7}, {3, 5},....{1,2,3,4,5,6} }.
На выходе должен быть массив массивов массивов :) вида:
{
{
{1}, {2,3}, {4,7}, {5}, {6,8},...
}
{
{1,2}, {3, 9}, {4,7}, {5}, {6,8},...
}
...
}
Любой набор массивов должен содержать все числа из набора и ни одно число не должно повторяться дважды. Итоговый набор этих наборов массивов должен быть полным (то есть содержать все возможные комбинации).
Отмечу, на всякий случай, что массив массивов, который есть во входных данных, может не содержать какие-либо из возможных комбинаций (например {1, 2, 3}). Соответственно, эта комбинация и НЕ должна рассматриваться далее.
...
Рейтинг: 0 / 0
07.07.2014, 12:01
| Ответить | Цитировать | Написать  
алгоритм
    #38689533
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexv,

Если немного переформулировать задачу,
то необходимо сгенерировать все перестановки,
которые состоят только из разрешенных циклов.

От этого и надо отталкиваться.
Упорядочить разрешенные циклы любым образом и перебрать.
...
Рейтинг: 0 / 0
07.07.2014, 15:28
| Ответить | Цитировать | Написать  
алгоритм
    #38689554
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

Честно скажу, я очень смутно понял, что нужно сделать)

На всякий случае, могу сказать, как я это первый раз планировал сделать:
сначала делается таблица вида (пусть N = 5):
11111
11112
...
12131
12133
...
12345

потом из нее сделал массивы массивов (соответственно):
{1,2,3,4,5}
{1,2,3,4},{5}
...
{1,3,5},{2},{4}
{1,3},{2},{4,5}
...
{1},{2},{3},{4},{5}

потом тупо пробежаться по списку и удалить все варианты, содержащие хотя бы один недоступный массив чисел (тот же {1,2,3}, например).

Но это все-таки не путь джедаев какой-то - сначала сгенерить все варианты и удалить ненужные)
...
Рейтинг: 0 / 0
07.07.2014, 15:42
| Ответить | Цитировать | Написать  
алгоритм
    #38689580
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexv,

Т.к. нам заранее неизвестно, сколько разрешенных циклов войдет в подстановку,
то проще всего алгоритм реализовать рекурсивно.

Если делать совсем в лоб, то потребуется глобальная переменная (или массив битов, если N велико),
в которой мы будем XOR'ом включать-выключать использованные циклы
и отсортированный массив разрешенных циклов (возможно разбитый на части по первому числу).

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

Возвращаемся по окончании цикла.
...
Рейтинг: 0 / 0
07.07.2014, 16:09
| Ответить | Цитировать | Написать  
алгоритм
    #38689621
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

Можете пояснить на примере? ) Допустим, у нас N = 4 (забегая вперед, максимальное количество N предполагается 20). Допустим, возможные комбинации:

{1}
{2}
{4}
{1,2}
{1,3}
{1,3,4}
{2,4}
{3,4}

честно говоря, я пока даже не понял, что именно подразумевается хранить в "глобальной переменной" и что именно вы называете "разрешенным циклом" (это один из "разрешенных массивов"?)
...
Рейтинг: 0 / 0
07.07.2014, 16:56
| Ответить | Цитировать | Написать  
алгоритм
    #38689646
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexvAleksandr Sharahov,

Можете пояснить на примере? ) Допустим, у нас N = 4 (забегая вперед, максимальное количество N предполагается 20). Допустим, возможные комбинации:

{1}
{2}
{4}
{1,2}
{1,3}
{1,3,4}
{2,4}
{3,4}

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

При таком N удобно и "занятость" элементов, и каждый "разрешенный массив", и части результата хранить в битах целого числа.
Чтобы при рекурсии было меньше параметров, часть из них, особенно если они не меняются между вызовами,
удобно делать глобальными. Это может немного ускорить процедуру.
Задача интересная, вечером, если будет время напишу подробнее с примером.

P.S. У цикла перестановки (подстановки) есть общеизвестное определение.
...
Рейтинг: 0 / 0
07.07.2014, 17:18
| Ответить | Цитировать | Написать  
алгоритм
    #38689654
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

"...P.S. У цикла перестановки (подстановки) есть общеизвестное определение. "

Если я упускаю какие-то общепринятые термины, прошу прощения). Образование мое далеко от программирования, а Кнута в одного раскурить я пока не готов).
...
Рейтинг: 0 / 0
07.07.2014, 17:29
| Ответить | Цитировать | Написать  
алгоритм
    #38689657
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexv,

ясно, просто я думал, так проще будет. Но, в общем, это и не требуется.
Думаю, для решения достаточно будет знания двоичной системы.
Позже отпишусь.
...
Рейтинг: 0 / 0
07.07.2014, 17:35
| Ответить | Цитировать | Написать  
алгоритм
    #38689824
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Решение под спойлером.
Каждый подсписок кодируется целым числом, биты которого соответствуют числам из подсписка.

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
unit AllowedPermForm;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  TCycle= integer;

const
  CycleBitCount=8*SizeOf(TCycle);
  AllCycles: array[0..7] of TCycle=
   ($01, $02, $03, $1C, $0C, $10, $07, $18);
   //{1},{2},{1,2},{3,4,5},{3,4},{5},{1,2,3},{4,5}

var
  MaxZeroIndex: integer;
  ZeroIndex: array of integer;
  UsedIndex: array[0..CycleBitCount-1] of integer;
  CycleIndex: array[0..CycleBitCount-1] of array of integer;

{Выдача из Print()
00000001  00000002  0000001C  
00000001  00000002  0000000C  00000010  
00000003  0000001C  
00000003  0000000C  00000010  
00000007  00000018  
}
procedure Print(Count: integer);
var
  i: integer;
  s: string;
begin;
  for i:=0 to Count-1 do s:=s + IntToHex(AllCycles[UsedIndex[i]], 8) + '  ';
  Form1.Memo1.Lines.Add(s);
  end;

function Init: boolean;
var
  i, j, k: integer;
  c, AllBits: TCycle;
begin;
  AllBits:=0;
  MaxZeroIndex:=-1;
  SetLength(ZeroIndex, Length(AllCycles));
  for i:=Low(CycleIndex) to High(CycleIndex) do CycleIndex[i]:=nil;
  for i:=Low(AllCycles) to High(AllCycles) do begin;
    c:=AllCycles[i];
    AllBits:=AllBits or c;
    if c<>0 then begin;
      j:=0;
      while c and 1=0 do begin;
        c:=c shr 1;
        inc(j);
        end;
      k:=Length(CycleIndex[j]);
      SetLength(CycleIndex[j], k+1);
      CycleIndex[j, k]:=i;
      while c and 1=1 do begin;
        c:=c shr 1;
        inc(j);
        end;
      ZeroIndex[i]:=j;
      if MaxZeroIndex<j then MaxZeroIndex:=j;
      end;
    end;
  Result:=(AllBits and (AllBits+1)=0);
  end;

procedure Generate(Count, BitNo: integer; Mask: TCycle);
var
  i, Index, NewBitNo: integer;
  c: TCycle;
begin;
  for i:=0 to Length(CycleIndex[BitNo])-1 do begin;
    Index:=CycleIndex[BitNo, i];
    c:=AllCycles[Index];
    if Mask and c=0 then begin;
      UsedIndex[Count]:=Index;
      NewBitNo:=ZeroIndex[Index];
      if NewBitNo=MaxZeroIndex then Print(Count+1)
      else Generate(Count+1, NewBitNo, Mask or c);
      end;
    end;
  end;

procedure TForm1.Button1Click(Sender: TObject);
begin;
  Memo1.Lines.Add('Начало работы');
  if Init then Generate(0,0,0);
  Memo1.Lines.Add('Конец работы');
  end;

end.

...
Рейтинг: 0 / 0
07.07.2014, 21:39
| Ответить | Цитировать | Написать  
алгоритм
    #38689830
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov,

исправил ошибку, теперь вроде все варианты находит

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
unit AllowedPermForm;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  TCycle= integer;

const
  CycleBitCount=8*SizeOf(TCycle);
  AllCycles: array[0..8] of TCycle=
   ($01, $02, $03, $05, $1C, $0C, $10, $07, $18);
   //{1},{2},{1,2},{1,4},{3,4,5},{3,4},{5},{1,2,3},{4,5}

var
  MaxZeroIndex: integer;
  ZeroIndex: array of integer;
  UsedIndex: array[0..CycleBitCount-1] of integer;
  CycleIndex: array[0..CycleBitCount-1] of array of integer;

{Выдача из Print()
00000001  00000002  0000001C
00000001  00000002  0000000C  00000010
00000003  0000001C  
00000003  0000000C  00000010
00000005  00000002  00000018
00000007  00000018
}
procedure Print(Count: integer);
var
  i: integer;
  s: string;
begin;
  for i:=0 to Count-1 do s:=s + IntToHex(AllCycles[UsedIndex[i]], 8) + '  ';
  Form1.Memo1.Lines.Add(s);
  end;

function Init: boolean;
var
  i, j, k: integer;
  c, AllBits: TCycle;
begin;
  AllBits:=0;
  MaxZeroIndex:=-1;
  SetLength(ZeroIndex, Length(AllCycles));
  for i:=Low(CycleIndex) to High(CycleIndex) do CycleIndex[i]:=nil;
  for i:=Low(AllCycles) to High(AllCycles) do begin;
    c:=AllCycles[i];
    AllBits:=AllBits or c;
    if c<>0 then begin;
      j:=0;
      while c and 1=0 do begin;
        c:=c shr 1;
        inc(j);
        end;
      k:=Length(CycleIndex[j]);
      SetLength(CycleIndex[j], k+1);
      CycleIndex[j, k]:=i;
      while c and 1=1 do begin;
        c:=c shr 1;
        inc(j);
        end;
      ZeroIndex[i]:=j;
      if MaxZeroIndex<j then MaxZeroIndex:=j;
      end;
    end;
  Result:=(AllBits and (AllBits+1)=0);
  end;

procedure Generate(Count, BitNo: integer; Mask: TCycle);
var
  i, Index, NewBitNo: integer;
  c, t, NewMask: TCycle;
begin;
  for i:=0 to Length(CycleIndex[BitNo])-1 do begin;
    Index:=CycleIndex[BitNo, i];
    c:=AllCycles[Index];
    if Mask and c=0 then begin;
      NewMask:=Mask or c;
      UsedIndex[Count]:=Index;
      NewBitNo:=ZeroIndex[Index];
      t:=1; t:=t shl NewBitNo;
      while t and NewMask<>0 do begin;
        t:=t+t; inc(NewBitNo);
        end;
      if NewBitNo=MaxZeroIndex then Print(Count+1)
      else Generate(Count+1, NewBitNo, NewMask);
      end;
    end;
  end;

procedure TForm1.Button1Click(Sender: TObject);
begin;
  Memo1.Lines.Add('Начало работы');
  if Init then Generate(0,0,0);
  Memo1.Lines.Add('Конец работы');
  end;

end.

...
Рейтинг: 0 / 0
07.07.2014, 22:00
| Ответить | Цитировать | Написать  
алгоритм
    #38689839
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov,

после исправления одна из проверок стала ненужной, упрощенная версия Generate():
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
procedure Generate(Count, BitNo: integer; Mask: TCycle);
var
  i, Index, NewBitNo: integer;
  c, NewMask: TCycle;
begin;
  for i:=0 to Length(CycleIndex[BitNo])-1 do begin;
    Index:=CycleIndex[BitNo, i];
    UsedIndex[Count]:=Index;
    NewMask:=Mask or AllCycles[Index];
    NewBitNo:=ZeroIndex[Index];
    c:=1; c:=c shl NewBitNo;
    while c and NewMask<>0 do begin;
      c:=c+c; inc(NewBitNo);
      end;
    if NewBitNo=MaxZeroIndex then Print(Count+1)
    else Generate(Count+1, NewBitNo, NewMask);
    end;
  end;
...
Рейтинг: 0 / 0
07.07.2014, 22:12
| Ответить | Цитировать | Написать  
алгоритм
    #38689840
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

Заранее прошу прощения за ламерский вопрос, но.. я правильно понял, это delphi? )
...
Рейтинг: 0 / 0
07.07.2014, 22:14
| Ответить | Цитировать | Написать  
алгоритм
    #38689846
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexv,

да
...
Рейтинг: 0 / 0
07.07.2014, 22:23
| Ответить | Цитировать | Написать  
алгоритм
    #38689861
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

Вопрос возник по поводу

($01, $02, $03, $05, $1C, $0C, $10, $07, $18);
//{1},{2},{1,2},{1,4},{3,4,5},{3,4},{5},{1,2,3},{4,5}

Я так понимаю, подразумевается следующее:

5/4/3/2/1 (числа)

0/0/0/0/1 = $01 = {1}
0/0/0/1/0 = $02 = {2}
0/0/0/1/1 = $03 = {1,2}
0/0/1/0/0 = $04 = {3}
0/0/1/0/1 = $05 = {1,3} - но у вас на этом месте упоминается {1,4}. Что я неправильно понимаю?
...
Рейтинг: 0 / 0
07.07.2014, 22:53
| Ответить | Цитировать | Написать  
алгоритм
    #38689872
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexv,

конечно, должно быть {1,3} - это я неверно прокомментировал
...
Рейтинг: 0 / 0
07.07.2014, 23:05
| Ответить | Цитировать | Написать  
алгоритм
    #38689894
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

Хорошо, еще вопрос (откровенно говоря, вопросов много :), просто для начала самые очевидные задам). В чем смысл конструкции:

while c and 1=0 do
begin;
c:=c shr 1;
inc(j);
end;

?
...
Рейтинг: 0 / 0
08.07.2014, 00:00
| Ответить | Цитировать | Написать  
алгоритм
    #38689896
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Дополню вопрос - имеется в виду часть условия: 1 = 0
...
Рейтинг: 0 / 0
08.07.2014, 00:01
| Ответить | Цитировать | Написать  
алгоритм
    #38689898
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexvAleksandr Sharahov,

Хорошо, еще вопрос (откровенно говоря, вопросов много :), просто для начала самые очевидные задам). В чем смысл конструкции:

while c and 1=0 do
begin;
c:=c shr 1;
inc(j);
end;

?

Это один из способов найти младший единичный бит в числе c,
мы просто в цикле сдвигаем число на 1 бит вправо до тех пор,
пока в младшей позиции не окажется единичный бит,
и считаем общее количество сдвигов.

Задавай другие.
...
Рейтинг: 0 / 0
08.07.2014, 00:05
| Ответить | Цитировать | Написать  
алгоритм
    #38689901
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexvДополню вопрос - имеется в виду часть условия: 1 = 0

там другое условие (c and 1)=0 ,
сравнение имеет низший приоритет
...
Рейтинг: 0 / 0
08.07.2014, 00:07
| Ответить | Цитировать | Написать  
алгоритм
    #38689905
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

Понял, спасибо

Следующий вопрос). Я уловить не могу, что же записывается в CycleIndex процедурой Init. Там конструкция ((0,2,3,7),(1),(4,5),(8),(6),...). Честно говоря, я даже предположить не могу, что эти числа означают.
...
Рейтинг: 0 / 0
08.07.2014, 00:22
| Ответить | Цитировать | Написать  
алгоритм
    #38689906
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
В частности, я не могу понять, почему они как-то похожи на итоговое решение (типа какие-то массивы с числами от 1 до 8, которые ни разу не повторяются), но решением не являются.
...
Рейтинг: 0 / 0
08.07.2014, 00:24
| Ответить | Цитировать | Написать  
алгоритм
    #38689909
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Что означают числа я понял, но логику их объединения в массивы пока что нет)
...
Рейтинг: 0 / 0
08.07.2014, 00:30
| Ответить | Цитировать | Написать  
алгоритм
    #38689913
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Вроде разобрался)

Я так понял, это списки номеров массивов, которые содержат соответственно 1, 2 (но без 1), 3 (но без 1 и 2), 4 (но без 1, 2, 3) и 5 (без остальных).
...
Рейтинг: 0 / 0
08.07.2014, 00:40
| Ответить | Цитировать | Написать  
алгоритм
    #38689914
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexvAleksandr Sharahov,

Понял, спасибо

Следующий вопрос). Я уловить не могу, что же записывается в CycleIndex процедурой Init. Там конструкция ((0,2,3,7),(1),(4,5),(8),(6),...). Честно говоря, я даже предположить не могу, что эти числа означают.

В CycleIndex[j, k] последовательно по k записываются индекы i всех элементов AllCycles[i], у которых j-тый бит равен 1.
...
Рейтинг: 0 / 0
08.07.2014, 00:41
| Ответить | Цитировать | Написать  
алгоритм
    #38689915
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
причем у них все биты младше j равны нулю
...
Рейтинг: 0 / 0
08.07.2014, 00:43
| Ответить | Цитировать | Написать  
алгоритм
    #38689918
balalexv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
balalexv
Гость
Aleksandr Sharahov,

Ну, в такой терминологии я кое-как из кода понял, мне же больше хочется понять физический смысл того, что хранится в переменных :).
...
Рейтинг: 0 / 0
08.07.2014, 00:47
| Ответить | Цитировать | Написать  
алгоритм
    #38689920
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
В ZeroIndex[i] для каждого AllCycles[i] записывается номеp младшего нулевого бита после первой серии единичных битов.
Это первое место, которое может оказаться не занято, после добавления соответствующего подсписка в текущий набор.
...
Рейтинг: 0 / 0
08.07.2014, 00:49
| Ответить | Цитировать | Написать  
алгоритм
    #38689921
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexvAleksandr Sharahov,

Ну, в такой терминологии я кое-как из кода понял, мне же больше хочется понять физический смысл того, что хранится в переменных :).

Смысл простой.
В начале набора может стоять только подсписок, в котором есть 1.
Перебираем их в цикле.
При этом каждый раз определяем первую свободную дырку.
Для очередной дырки перебираем все подсписки, кот. начинаются с такого элемента.
Если подсписок допустим, идем дальше.
Повторяем до победного конца.
...
Рейтинг: 0 / 0
08.07.2014, 00:54
| Ответить | Цитировать | Написать  
алгоритм
    #38689931
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov,

Все-таки в 16272074 - самый правильный код.

Упрощенная процедура Generate() из 16272101 работает неверно и дает много грязи,
т.к. не проверяет допустимость очередного подсписка - это я ужинал, кровь от мозга оттекла наверно.

Жалко нельзя тут без помощи модератора удалить сообщение.
Если заглянет кто сюда, удалите 16272101 .
...
Рейтинг: 0 / 0
08.07.2014, 01:17
| Ответить | Цитировать | Написать  
алгоритм
    #38690163
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
balalexv,

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

 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
//Cгенерировать все перестановки, которые состоят только из разрешенных циклов,
//например, перестановки длиной 5 из циклов {1},{2},{1,2},{1,4},{3,4,5},{3,4},{5},{1,2,3},{4,6},{3,5},{4},{1,5}.

unit AllowedPermForm;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  TCycle= integer;

const
  CycleBitCount=8*SizeOf(TCycle);
  AllCycles: array[0..11] of TCycle=
   ($01, $02, $03, $09, $1C, $0C, $10, $07, $18, $14, $08, $11);
   //{1},{2},{1,2},{1,4},{3,4,5},{3,4},{5},{1,2,3},{4,6},{3,5},{4},{1,5}

var
  LastBitNo: integer;
  ZeroIndex: array of integer;
  UsedIndex: array[0..CycleBitCount-1] of integer;
  CycleIndex: array[0..CycleBitCount-1] of array of integer;

{
Выдача из Init:
LastBitNo = 4
ZeroIndex = 1  2  2  1  5  4  5  3  5  3  4  1
CycleIndex[0] = 0  2  3  7  11
CycleIndex[1] = 1
CycleIndex[2] = 4  5  9
CycleIndex[3] = 8  10
CycleIndex[4] = 6

Выдача из Print:
00000001  00000002  0000001C
00000001  00000002  0000000C  00000010
00000001  00000002  00000014  00000008
00000003  0000001C
00000003  0000000C  00000010
00000003  00000014  00000008
00000009  00000002  00000014
00000007  00000018
00000007  00000008  00000010
00000011  00000002  0000000C
}

procedure Print(Count: integer);
var
  i: integer;
  s: string;
begin;
  for i:=0 to Count-1 do s:=s + IntToHex(AllCycles[UsedIndex[i]], 8) + '  ';
  Form1.Memo1.Lines.Add(s);
  end;

function Init: boolean;
var
  i, j, k: integer;
  c, AllBits: TCycle;
//  s: string;
begin;
  AllBits:=0;
  SetLength(ZeroIndex, Length(AllCycles));
  for i:=Low(CycleIndex) to High(CycleIndex) do CycleIndex[i]:=nil;
  for i:=Low(AllCycles) to High(AllCycles) do begin;
    c:=AllCycles[i];
    AllBits:=AllBits or c;
    if c<>0 then begin;
      j:=0;
      while c and 1=0 do begin;
        c:=c shr 1;
        inc(j);
        end;
      k:=Length(CycleIndex[j]);
      SetLength(CycleIndex[j], k+1);
      CycleIndex[j, k]:=i;
      while c and 1=1 do begin;
        c:=c shr 1;
        inc(j);
        end;
      ZeroIndex[i]:=j;
      end;
    end;
  Result:=(AllBits and (AllBits+1)=0);
  LastBitNo:=-1;
  while AllBits<>0 do begin;
    AllBits:=AllBits shr 1;
    inc(LastBitNo);
    end;
{
  Form1.Memo1.Lines.Add(Format('LastBitNo = %d',[LastBitNo]));
  s:='ZeroIndex = '; for i:=0 to Length(ZeroIndex)-1 do s:=s + IntToStr(ZeroIndex[i]) + '  ';
  Form1.Memo1.Lines.Add(s);
  for j:=0 to LastBitNo do begin;
    s:=Format('CycleIndex[%d] = ',[j]);
    for i:=0 to Length(CycleIndex[j])-1 do s:=s + IntToStr(CycleIndex[j,i]) + '  ';
    Form1.Memo1.Lines.Add(s);
    end;
}
  end;

procedure Generate(Count, BitNo: integer; Mask: TCycle);
var
  i, Index, NewBitNo: integer;
  c, t, NewMask: TCycle;
begin;
  for i:=0 to Length(CycleIndex[BitNo])-1 do begin;
    Index:=CycleIndex[BitNo, i];
    c:=AllCycles[Index];
    if Mask and c=0 then begin;
      NewMask:=Mask or c;
      UsedIndex[Count]:=Index;
      NewBitNo:=ZeroIndex[Index];
      t:=1; t:=t shl NewBitNo;
      while t and NewMask<>0 do begin;
        t:=t+t; inc(NewBitNo);
        end;
      if NewBitNo>LastBitNo then Print(Count+1)
      else Generate(Count+1, NewBitNo, NewMask);
      end;
    end;
  end;

procedure TForm1.Button1Click(Sender: TObject);
begin;
  Memo1.Lines.Add('Начало работы');
  if Init then Generate(0,0,0);
  Memo1.Lines.Add('Конец работы');
  end;

end.

...
Рейтинг: 0 / 0
08.07.2014, 11:18
| Ответить | Цитировать | Написать  
алгоритм
    #38690175
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Обращаю внимание на то, что комментарии к данным могут не совсем соответствовать самим данным.
Это из-за того, я при экспериментах не всегда правил комментарии.
В частности, вижу, что в комментарии стоит цикл {4,6} вместо {4,5}.
...
Рейтинг: 0 / 0
08.07.2014, 11:28
| Ответить | Цитировать | Написать  
31 сообщений из 31, показаны все 2 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1341302]:
 0ms
get settings:
 12ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 228ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 68ms
get tp. blocked users:
 2ms
others: 250ms
total:  594ms
созд. / загр.: 594ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]