0

I have a matrix like:

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

in code:

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' }
};

I need to get all possible combination of this matrix with 5 chars each, but every char must be the next immediate neighbor, for instance, 0,5 and 4,8 are invalid but 0,6 and 3,4 are valid.

This matrix will not be static as is in the sample, it is generated with the hex numbers in any position every time.

Thanks!

mac
  • 42,153
  • 26
  • 121
  • 131
Bruno
  • 4,337
  • 12
  • 42
  • 55
  • what have you tied? or you looking for people who will do work for you? – Renatas M. Nov 29 '11 at 11:51
  • no, I'm looking for help, which is the purpose of this site I think? what I do atm is generate all possible combinations of the hex numbers and then I check if it's valid in the array, but it's too slow and not good for production – Bruno Nov 29 '11 at 11:55
  • 1
    is this homework? and what do you mean by "5 chars each"? – DarkSquirrel42 Nov 29 '11 at 12:07
  • no, it's not homework, what is the problem with this question? I just found this http://stackoverflow.com/questions/4339503/all-possible-combinations-of-numbers-of-length-5-in-a-4x4-matrix which is exactly the same thing I'm asking but it ins python and I don't know how to convert it. 5 chars each combination is what I mean – Bruno Nov 29 '11 at 12:09
  • So ok show what you already got, maybe we can speed it up or tell what you doing wrong. Now you question looks like `give me the code!`. Try to understand...if I write you entire algorithm, spend my time to do that...and at the end who will get payed that this peace of code will be good for production? – Renatas M. Nov 29 '11 at 12:09
  • Appears to be a duplicate: http://stackoverflow.com/questions/4339503/all-possible-combinations-of-numbers-of-length-5-in-a-4x4-matrix – Mr.Wizard Nov 29 '11 at 21:56

1 Answers1

1

Just for fun - Delphi code. 'shl' is left shift (<<), strings are one-based. Borders are added around the matrix as sentinels to simplify checks.

Some additional comments: I use 6x6 matrix - 4x4 core with digits, and one-cell width outer border. 36 bits of Int64 are used as sentinels. Bit value of 1 denotes border or visited cell. Procedure StartTravel initiates path finding from some starting cell of core. Path finding goes like DFS (deep-first search), but interrupts when path length becomes 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
MBo
  • 77,366
  • 5
  • 53
  • 86