ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм
25 сообщений из 31, страница 1 из 2
  1  все
алгоритм
    #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
| Ответить | Цитировать | Написать  
25 сообщений из 31, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38689901&tid=1341302]:
 0ms
get settings:
 7ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 166ms
get topic data:
 8ms
get forum data:
 3ms
get page messages:
 71ms
get tp. blocked users:
 1ms
others: 212ms
total:  488ms
созд. / загр.: 488ms
x
x
Закрыть


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