使用因式的第k个置换

Question

我想找出k的大值的从1到n的第k个排列，我发现了一个叫做因式的方法，但我不能实现它。任何其他方法也将是有用的。有人能帮上忙吗？

Answer 1

在阅读了大量的白皮书和维基百科之后，我最终得出了这个结论(注意:排列是从0开始的，而不是从1开始的)

测试代码

    [Test]
    public void Permutation_0_Returns_0123456789()
    {
        int[] factoradic = 0.ToFactoradic(10);
        int[] permutation = factoradic.ToPermutation(10);
        int[] expected = { 0,1,2,3,4,5,6,7,8,9 };
        Assert.AreEqual(expected, permutation);
    }
    [Test]
    public void Permutation_1_Returns_0123456798()
    {
        int[] factoradic = 1.ToFactoradic(10);
        int[] permutation = factoradic.ToPermutation(10);
        int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 9, 8 };
        Assert.AreEqual(expected, permutation);
    }

实现

public static class IntExtensions
{
    //http://en.wikipedia.org/wiki/Factorial_number_system
    public static int[] ToFactoradic(this int value, int digitCount)
    {
        var factoradic = new int[digitCount];
        //Repeatedly divide by an increasing number
        //The reverse of the remainders forms the factoradic
        for (var i = 1; i <= digitCount; i++)
        {
            factoradic[digitCount - i] = value % i;
            value /= i;
        }
        return factoradic;
    }

    public static int[] ToPermutation(this int[] value, int digitCount)
    {
        //Initialise the digit list
        var digitList = new List<int>(digitCount);
        for (int i = 0; i < digitCount; i++)
        {
            digitList.Add(i);
        }
        //Loop through the factoradic pulling out each value in turn
        // Use this value as an index into the digit list removing each digit as it's used
        var permutationList = new List<int>(digitCount);
        for (var i = 0; i < value.Length; i++)
        {
            int indexIntoDigitList = value[i];
            int atom = digitList[indexIntoDigitList];
            digitList.RemoveAt(indexIntoDigitList);
            permutationList.Add(atom);
        }

        return permutationList.ToArray();
    }
}

Answer 2

这是一篇关于C#实现的微软文章：http://msdn.microsoft.com/en-us/magazine/cc163513.aspx

编辑:这里是一个多汁的部分的粘贴(抱歉，缺少格式-这是它在源文章中的方式)

public StringPerm(string[] atoms, int k) 
{
    this.element = new string[atoms.Length]; 
    this.order = atoms.Length; 

    // Step #1 - Find factoradic of k 
    int[] factoradic = new int[this.order]; 
    for (int j = 1; j <= this.order; ++j) 
    { 
        factoradic[this.order - j] = k % j; 
        k /= j; 
    } 

    // Step #2 - Convert factoradic[] to numeric permuatation in perm[] 
    int[] temp = new int[this.order]; 
    int[] perm = new int[this.order]; 
    for (int i = 0; i < this.order; ++i) 
    {
         temp[i] = ++factoradic[i]; 
    }
    perm[this.order - 1] = 1; 
    // right-most value is set to 1. 

    for (int i = this.order - 2; i >= 0; --i) 
    {
        perm[i] = temp[i]; 
        for (int j = i + 1; j < this.order; ++j) 
        {
            if (perm[j] >= perm[i]) 
            ++perm[j]; 
        }
    } 
    for (int i = 0; i < this.order; ++i) // put in 0-based form 
        --perm[i];

    // Step #3 - map numeric permutation to string permutation 
    for (int i = 0; i < this.order; ++i) 
        this.element[i] = atoms[perm[i]]; 
}

Answer 3

private static String nextPermutationSequence(int N, int k){

        int nMinusOneFactorial = 1;
        List<Integer> list = new ArrayList<Integer>();
        StringBuilder buf = new StringBuilder();

        for(int i=1;i<=N;i++){
            list.add(i);
            nMinusOneFactorial*=i;
        }

        k=k-1;
        nMinusOneFactorial=nMinusOneFactorial/N;

        for(int i=N-1;i>=1;i--){

            int position = k/nMinusOneFactorial;
            int val = list.get(position);
            buf.append(Integer.valueOf(val));
            list.remove(position);
            k = k%nMinusOneFactorial;
            nMinusOneFactorial=nMinusOneFactorial/i;

        }

        buf.append(Integer.valueOf(list.get(0)));
        return buf.toString();
    }