乐趣区

关于c:Permutation-Sequence

The set [1, 2, 3, …, n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

“123”
“132”
“213”
“231”
“312”
“321”

Given n and k, return the kth permutation sequence.

思路:
通过给定的 n 和 k,一直的递加 n,获取每一次的数组的索引值及 k 的新值,直到 n 为 0,终止循环
将获取的每一次的索引值,从数组(数据每一次取值后,都须要删除该值)内取出值即可。

int* copyIntList(int* list, int length) {int* result = (int*)malloc(length * sizeof(int));

    for (int i = 0; i < length; i++) {result[i] = list[i];
    }

    return result;
}

int getIndex(int n, int k) {return (double)ceil((double)k / getFabric(n - 1)) - 1;
}

int getFabric(int n) {if (n == 0) return 1;
    int total = 1;
    for (int i = 1; i <= n; i++) {total *= i;}
    return total;
}

void deleteElementByIndex(int* list, int length, int position) {for (int i = position; i < length; i++) {list[i - 1] = list[i];
    }
}

char* getPermutationSequenceByIndex(int* list, int n, int k) {
    int _n = n, _k = k;
    int* _list = copyIntList(list, n);

    char* result = (char*)malloc((n + 1) * sizeof(char));
    result[n] = '\0';
    int curResultIndex = 0;

    while (_n > 0) {int curIndex = (int)getIndex(_n, _k);
        //dosomething 1.get index from list , then remove the index val of list;
        result[curResultIndex] = '0' + _list[curIndex];
        curResultIndex++;
        deleteElementByIndex(_list, _n, curIndex + 1);

        int nextLen = getFabric(_n - 1);
        int nextK = _k % nextLen == 0 ? nextLen : _k % nextLen;
        _k = _k <= nextLen ? _k : nextK;
        _n--;
    }

    free(_list);
    return result;
}

char* getPermutation(int n, int k) {
    // 生成 int 动静数组
    int* p = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {p[i] = i + 1;
    }
    char* result = getPermutationSequenceByIndex(p, n, k);
    free(p);
    return result;
}
退出移动版