Генерация всех путей через матрицу с максимальным N сходством с любым другим

Question

У меня есть матрица X by Y, и из этого мне нужно сгенерировать все возможные способы перехода из одной стороны (первый столбец) в другую (последний столбец), но только N точек на пути могут бытькак и любая другая сгенерированная комбинация.

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

Есть ли способ сгенерировать комбинации с максимальным N в сходстве без необходимости их генерации?

Пример: N = 1

["a", "a", "a"]
["b", "b", "b"]
["c", "c", "c"]

Должно сгенерировать что-то вроде этого: aaa abb acc bba cca cab

Я занимался этим несколько дней назад и не нашел хороших решений, поэтому любая помощь будетс благодарностью и, если возможно, в C #.

Answer 1

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

Существует оптимальная подструктура в том смысле, что пути - это просто сумма независимых, но перекрывающихся префиксов (a + a = aa, aa + a = aaa). Принимая это во внимание, мы можем решить проблему 3х3 следующим образом.

Метод бумаги и карандаша:

Определение решения первого выбора уже сделано - а, б, в. Нам нужно определить решение второго выбора, третьего и т. Д.

Определить префиксы для двух по конкатенации row + col - выбор доступен из двух столбцов.

    a   b   c
a   aa  ab  ac
b   ba  bb  bc
c   ca  cb  cc

Возьмите только что созданные префиксы и примените их к нашему исходному решению 1x1 - row + col

    a   b   c
aa  aaa aab aac
ba  baa bab bac
ca  caa cab cac
ab  aba abb abc
bb  bba bbb bbc
cb  cba cbb cbc
ac  aca acb acc
bc  bca bcb bcc
cc  cca ccb ccc

Решением n * n будет просто повторение этого метода n-1 раз.

Я написал это также на C #

class Program
{
    static void Main(string[] args)
    {
        int sizeOf = 3; //size of problem - ex 3x3
        var vals = "abcdefghijklmnop".ToCharArray(); //up to 16 (abc in ex)

        //Create initial problem
        String[] x = new String[sizeOf]; 
        String[] y = new String[sizeOf];

        for (int i = 0; i < x.Length; i++)
        {
            x[i] = vals[i].ToString();
            y[i] = vals[i].ToString();
        }

        //hold our solutions
        String[][] result = null;
        String[] temp = x;

        for (int i = 1; i < y.Length; i++)
        {
            result = getCombos(temp, y);

            temp = (from k in result
                    from l in k
                    select l).ToArray();
        }

        //Flatten out solution
        var finalResult = (from k in result
                           from l in k
                           select l).ToList();

        printArray(finalResult);
        Console.WriteLine("Total Count: {0}", finalResult.Count());

    }

    static void printArray(List<String> a)
    {
        foreach (var x in a)
        {
            Console.Write("{0} ", x);
        }
        Console.WriteLine();
    }

    static String[][] getCombos(String[] x, String[] y)
    {
        //Initialize array to hold solution
        String[][] prefixes = new String[x.Length][];
        for (int j = 0; j < x.Length; j++)
        {
            prefixes[j] = new String[y.Length];
        }

        //concat to form solution
        for (var i = 0; i < x.Length; i++)
        {
            for (var j = 0; j < y.Length; j++)
            {
                prefixes[i][j] = x[i] + y[j];
            }
        }
        return prefixes;
    }
}

Я довел это до 9х9, пока космическая сложность не стала слишком большой. Это очень интересная проблема.

Answer 2

Ответ = y ^ (x - n)

Игнорируйте вашу проблему в первую очередь и обобщите, у вас есть сетка 3x3. Итак:

x = 3;
y = 3;
n = 1;

Поэтому у вас есть у ^ х комбинаций, то есть 3 ^ 3 = 27

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

В вашем примере N равно единице, поэтому уменьшите x на 1, чтобы получить x, равное 2.

Теперь 3 ^ 2 = 6, что является вашим ответом.

Если бы вы увеличили это, я думаю, это было бы точно, но у меня была длинная неделя, поэтому, если я что-то пропустил, пожалуйста, дайте мне знать.

Редактировать Перечитав ваш вопрос, я не совсем уверен, что правильно понял, я заинтригован, поэтому, пожалуйста, дайте мне знать ...