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

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

1 голос
/ 21 июня 2009

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

Если длина ввода равна четырем, то все перестановки 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, когда число таблиц равно больше двух.)

Ответы [ 2 ]

1 голос
/ 31 августа 2009

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

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

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

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

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

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

0 голосов
/ 21 июня 2009

Подход грубой силы в 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()
...