Find the permutations where no element stays in place

Question

I'm working with permutations where each element is different from its original location. I would like an algorithm that given {an input length, row and digit}, will give me the output number. Here's an example:

If the input length is four, then all the permutations of 0123 are:

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

The permutations in which no digit is in the same place (every digit has moved):

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

Numbering starts at 0 so if the input to the function is {4,0,0}, the output should be the 0th (leftmost) digit of the 0th (first) permutation. First digit of 1032 is 1.

If the input is {4,1,1} then the output is the the second digit of 1230, which is 2.

The row number might be greater the nubmer of permutations. In that case, take the remainder modulo the number of permutations (in the above case, row modulo 9).

In the c language would be great.

(It's not homework, it's for work. Cuckoo hashing if you must know. I'd like to randomly select the swaps that I'll be making at each stage to see if it's better than BFS when the number of tables is greater than two.)

Answer 1

Brute-force approach in Python (you may use it to test your C implementation):

#!/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

Why not just build a tree and iterate through it?

For example, if you have the digits 0123, then you know that the left most digit can be only from the set {1,2,3}. This would act as your first level in your tree.

Then, if you go down the path beginning with 1, you only have three options, {0, 2, 3}. If you go down the path beginning with 2 in the first level, you only have two options {0,3} (since you can't use 1 in the second digit from the left and the 2 was already used (you could pop the 2 from your list of choices)), etc.

The thing to watch out for in this approach is if you get to the end of a branch with 3 being your only option, in which case, you would just delete it.

For n > 10 generating all permutations and then filtering can become problematic. I think building out the tree would trim this significantly.

You can build the tree on the fly if need be. Your order can be defined by how you traverse the tree.