Найдите перестановки, где ни один элемент не остается на месте

Question

Я работаю с перестановками, в которых каждый элемент отличается от своего исходного местоположения. Я хотел бы, чтобы алгоритм, который {длина ввода, строка и цифра}, дал мне выходной номер. Вот пример:

Если длина ввода равна четырем, то все перестановки 0123:

0123,0132,0213,0231,0312,0321,
1023,1032,1203,1230,1302,1320,
2013,2031,2103,2130,2301,2310,
3012,3021,3102,3120,3201,3210

Перестановки, в которых ни одна цифра не находится в одном и том же месте (каждая цифра переместилась):

1032,1230,1302,
2031,2301,2310,
3012,3201,3210

Нумерация начинается с 0, поэтому если входные данные для функции {4,0,0}, выходные данные должны быть 0-й (самой левой) цифрой 0-й (первой) перестановки. Первая цифра 1032 - 1.

Если входное значение равно {4,1,1}, то выходным значением является вторая цифра 1230, то есть 2.

Номер строки может быть больше числа перестановок. В этом случае возьмите остаток по модулю количества перестановок (в приведенном выше случае строка по модулю 9).

На языке c было бы здорово.

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

Answer 1

Подход грубой силы в Python (вы можете использовать его для тестирования вашей реализации C):

#!/usr/bin/env python
from itertools import ifilter, islice, permutations

def f(length, row, digit):
    """
    >>> f(4, 0, 0)
    1
    >>> f(4, 1, 1)
    2
    """
    # 1. enumerate all permutations of range (range(3) -> [0,1,2], ..)
    # 2. filter out permutations that have digits inplace
    # 3. get n-th permutation (n -> row)
    # 4. get n-th digit of the permutation (n -> digit)
    return nth(ifilter(not_inplace, permutations(range(length))), row)[digit]

def not_inplace(indexes):
    """Return True if all indexes are not on their places.

    """
    return all(i != d for i, d in enumerate(indexes))

def nth(iterable, n, default=None):
    """Return the nth item or a default value.

    http://docs.python.org/library/itertools.html#recipes
    """
    return next(islice(iterable, n, None), default)

if __name__=="__main__":
    import doctest; doctest.testmod()

Answer 2

Почему бы просто не построить дерево и не пройтись по нему?

Например, если у вас есть цифры 0123 , то вы знаете, что самая левая цифра может быть только из набора {1,2,3} . Это будет действовать как ваш первый уровень в вашем дереве.

Затем, если вы идете по пути, начинающемуся с 1, у вас есть только три варианта: {0, 2, 3} . Если вы идете по пути, начинающемуся с 2 на первом уровне, у вас есть только две опции {0,3} (поскольку вы не можете использовать 1 во второй цифре слева и 2 уже используется (вы можете вытолкнуть 2 из списка вариантов) и т. д.

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

Для n > 10 генерация всех перестановок и последующая фильтрация могут стать проблематичными. Я думаю, что построение дерева значительно обрезало бы это.

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