Все комбинации матрицы 4х4 с 5 символами - PullRequest
Новая
       22

Все комбинации матрицы 4х4 с 5 символами

0 голосов
/ 29 ноября 2011

У меня есть матрица вроде: 

0 | 1 | 2 | 3
-------------
7 | 6 | 5 | 4
-------------
8 | 9 | A | B
-------------
F | E | D | C

в коде: 

var matrix = new char[][]
{ 
    new char[] { '0', '1', '2', '3' },
    new char[] { '7', '6', '5', '4' },
    new char[] { '8', '9', 'A', 'B' },
    new char[] { 'F', 'E', 'D', 'C' }
};

Мне нужно получить все возможные комбинации этой матрицы с 5 символами каждый, но каждый символ должен быть следующим непосредственным соседом, например, 0,5 и 4,8 недействительны, но 0,6 и 3,4 действительны .

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

Спасибо!

Ответы [ 2 ]

1 голос
/ 29 ноября 2011

Просто для удовольствия - код Delphi. 'shl' - сдвиг влево (<<), строки основаны на единицах. Границы добавляются вокруг матрицы как часовые для упрощения проверок. </p>

Некоторые дополнительные комментарии: я использую матрицу 6x6 - ядро ​​4x4 с цифрами и внешнюю границу шириной в одну ячейку. 36 бит Int64 используются в качестве часовых. Битовое значение 1 обозначает границу или посещенную ячейку. Процедура StartTravel инициирует поиск пути из некоторой начальной ячейки ядра. Поиск пути происходит как DFS (глубокий поиск), но прерывается, когда длина пути становится равной 5. 

const
  Directions: array[0..3] of Integer = (-1, -6, 1, 6);

var
  Digits: string;
  Mask: Int64;
  i, j: Integer;

  procedure Travel(AFrom: Integer; Visited: Int64; Path: string);
  var
    i, Dir: Integer;
    NewMask: Int64;
  begin
    if Length(Path) = 5 then
      PrintOut(Path)
    else
      for i := 0 to 3 do begin
        Dir := Directions[i];
        NewMask := 1 shl (AFrom + Dir);
        if (Visited and NewMask) = 0 then
          Travel(AFrom + Dir, Visited or NewMask, Path + Digits[AFrom + Dir + 1]);
      end;
  end;

  procedure Init;
  var
    i: Integer;
  begin
    Digits := '-------0123--7654--89AB--FEDC-------';
    Mask := 0;
    for i := 1 to Length(Digits) do
      if Digits[i] = '-' then
        Mask := Mask or (1 shl (i - 1));
  end;

  procedure StartTravel(Row, Col: Integer);
  var
    APos: Integer;
  begin
    APos := Row * 6 + Col + 7;
    Travel(APos, Mask or (1 shl APos), Digits[APos + 1]);
  end;

begin
  Init;
  for i := 0 to 3 do
    for j := 0 to 3 do
      StartTravel(i, j);

432 combinations:
01234
01256
01254
0125A
01678
01652
01654
0165A
01698
0169A
0169E
07612
07652
....
CBADE
CB456
CB452
CB45A
CB432
1 голос
/ 29 ноября 2011

Все возможные комбинации массива

Генерация всех возможных комбинаций

Это может вам помочь. Кстати, пожалуйста, поверьте в "поиск"

...