Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм / 25 сообщений из 31, страница 1 из 2
  1  все
07.07.2014, 12:01
    #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, 15:28
    #38689533
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
balalexv,

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

От этого и надо отталкиваться.
Упорядочить разрешенные циклы любым образом и перебрать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.07.2014, 15:42
    #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, 16:09
    #38689580
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
balalexv,

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

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

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

Возвращаемся по окончании цикла.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.07.2014, 16:56
    #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, 17:18
    #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:29
    #38689654
balalexv
balalexv
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
Aleksandr Sharahov,

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

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

ясно, просто я думал, так проще будет. Но, в общем, это и не требуется.
Думаю, для решения достаточно будет знания двоичной системы.
Позже отпишусь.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.07.2014, 21:39
    #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, 22:00
    #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:12
    #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:14
    #38689840
balalexv
balalexv
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
Aleksandr Sharahov,

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

да
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.07.2014, 22:53
    #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, 23:05
    #38689872
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
balalexv,

конечно, должно быть {1,3} - это я неверно прокомментировал
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.07.2014, 00:00
    #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:01
    #38689896
balalexv
balalexv
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
Дополню вопрос - имеется в виду часть условия: 1 = 0
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.07.2014, 00:05
    #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:07
    #38689901
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
balalexvДополню вопрос - имеется в виду часть условия: 1 = 0

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

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

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

Я так понял, это списки номеров массивов, которые содержат соответственно 1, 2 (но без 1), 3 (но без 1 и 2), 4 (но без 1, 2, 3) и 5 (без остальных).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.07.2014, 00:41
    #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:43
    #38689915
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм
причем у них все биты младше j равны нулю
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм / 25 сообщений из 31, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 359ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1341302]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 40ms
get topic data:
 12ms
get forum data:
 2ms
get page messages:
 69ms
get tp. blocked users:
 2ms
others: 204ms
total:  359ms
x
x
Закрыть


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