Все возможные комбинации длины 8 в двумерном массиве

Question

Я пытался решить проблему в комбинациях.У меня есть матрица 6X6. Я пытаюсь найти в матрице все комбинации длины 8.

Мне нужно перейти от соседа к соседу из каждой строки, позиции столбца, и я написал рекурсивную программу, которая генерирует комбинациюно проблема в том, что он генерирует много дубликатов, а значит, неэффективен.Я хотел бы знать, как я могу устранить подсчет дубликатов и сэкономить время.

int a={{1,2,3,4,5,6},
   {8,9,1,2,3,4},
   {5,6,7,8,9,1},
   {2,3,4,5,6,7},
   {8,9,1,2,3,4},
   {5,6,7,8,9,1},
  }

 void genSeq(int row,int col,int length,int combi)
 {
    if(length==8)
    {
      printf("%d\n",combi);
      return;
    }
    combi = (combi * 10) + a[row][col];
    if((row-1)>=0)

    genSeq(row-1,col,length+1,combi);

if((col-1)>=0)

    genSeq(row,col-1,length+1,combi);

if((row+1)<6)

    genSeq(row+1,col,length+1,combi);

if((col+1)<6)

    genSeq(row,col+1,length+1,combi);

if((row+1)<6&&(col+1)<6)

    genSeq(row+1,col+1,length+1,combi);

if((row-1)>=0&&(col+1)<6)

    genSeq(row-1,col+1,length+1,combi);

if((row+1)<6&&(row-1)>=0)

    genSeq(row+1,col-1,length+1,combi);

if((row-1)>=0&&(col-1)>=0)

    genSeq(row-1,col-1,length+1,combi);
   }

Я также думал о написании динамической программы, в основном рекурсии с запоминанием.Это лучший выбор?если да, то мне не понятно, как реализовать это в рекурсии.Действительно ли я зашел в тупик с подходом ???

Спасибо

Изменить Например, результат 12121212,12121218,12121219,12121211,12121213.

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

Answer 1

Для исключения дубликатов вы можете преобразовать 8-значные последовательности в 8-значные целые и поместить их в хеш-таблицу.

Памятка может быть хорошей идеей. Вы можете запомнить для каждой ячейки в матрице все возможные комбинации длины 2-7, которые могут быть получены из нее. Возвращаясь назад: сначала сгенерируйте для каждой ячейки все последовательности из 2 цифр. Затем на основе 3 цифры и т. Д.

ОБНОВЛЕНИЕ: код на Python

# original matrix
lst = [
   [1,2,3,4,5,6],
   [8,9,1,2,3,4],
   [5,6,7,8,9,1],
   [2,3,4,5,6,7],
   [8,9,1,2,3,4],
   [5,6,7,8,9,1]]

# working matrtix; wrk[i][j] contains a set of all possible paths of length k which can end in lst[i][j]
wrk = [[set() for i in range(6)] for j in range(6)]

# for the first (0rh) iteration initialize with single step paths
for i in range(0, 6):
    for j in range(0, 6):
        wrk[i][j].add(lst[i][j])

# run iterations 1 through 7
for k in range(1,8):
    # create new emtpy wrk matrix for the next iteration
    nw = [[set() for i in range(6)] for j in range(6)]

    for i in range(0, 6):
        for j in range(0, 6):
            # the next gen. wrk[i][j] is going to be based on the current wrk paths of its neighbors
            ns = set()
            if i > 0:
                for p in wrk[i-1][j]:
                    ns.add(10**k * lst[i][j] + p)
            if i < 5:
                for p in wrk[i+1][j]:
                    ns.add(10**k * lst[i][j] + p)
            if j > 0:
                for p in wrk[i][j-1]:
                    ns.add(10**k * lst[i][j] + p)
            if j < 5:
                for p in wrk[i][j+1]:
                    ns.add(10**k * lst[i][j] + p)

            nw[i][j] = ns
    wrk = nw

# now build final set to eliminate duplicates
result = set()

for i in range(0, 6):
    for j in range(0, 6):
        result |= wrk[i][j]

print len(result)
print result

Answer 2

Вы можете думать о своей матрице так, как будто это одномерный массив - неважно, здесь («размещайте» строки одну за другой). Для одномерного массива вы можете написать функцию типа (при условии, что вы должны напечатать комбинации)

f(i, n) prints all combinations of length n using elements a[i] ... a[last].

Следует пропустить некоторые элементы из a [i] в ​​a [i + k] (для всех возможных k), вывести a [k] и сделать рекурсивный вызов f (i + k + 1, n - 1).

Answer 3

int a={{1,2,3,4,5,6}, {8,9,1,2,3,4}, {5,6,7,8,9,1}, {2,3,4,5,6,7}, {8,9,1,2,3,4}, {5,6,7,8,9,1}, }

По длине вы имеете в виду суммирование комбинации матричных элементов, получающихся в результате 8.
т.е. элементы для суммирования 8 с самой строкой и с другими элементами строки.
Из строки 1 = {{2,6}, {3,5},}, а теперь и элементов строки 1 со строкой 2 и так далее.Это то, что вы ожидаете?

Answer 4

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

Я не специалист по алгоритмам, но уверен, что есть действительно умные способы сделать это, чтобыбудет публиковать после меня.

Кроме того, в Java при использовании CamelCase, имена методов должны начинаться со строчной буквы.