排列顺序的计算 [英] calculation of permutation sequence
问题描述
我正在下面的问题和后code我调试和问题的声明。其实我试着找了几个参考的解决方案，而且都没有过多的解释类似。如果有人可以帮助解释如下逻辑的作品，这将是巨大的。我用为（i = 0，K循环特别是困惑 - ;我
集合[1,2,3，...，N]共包含n个！独特的排列。
通过上市，才能标注所有的排列，
我们得到如下序列（即，对于n = 3）：
123
132
213
231
312
321
由于氮，钾，返回的第k个排列顺序。
注：给定n为9（含）之间1和。
code基准
的#include＆LT;的iostream＆GT;
使用名字空间std;
字符串getPermutation（INT N，INT K）{
INT I，J，F = 1;
第//左边是部分形成置换，右边是剩下的字符。
串S（N，'0'）;
对于（i = 1; I＆LT; = N;我++）{
F * =我;
S [I-1] + = I; //使小号成为1234 ... N
}
为（ⅰ= 0中，k - ;我n种;我++）{
F / = N-I;
J = I + K / F; //计算字符的指数将在S [I]
焦炭C = S [J]。
//通过转移来掩盖（调整右侧部分）删除℃。
对于（; J＆GT;我; j--）
S [J] = S [J-1]。
ķ％= F;
S [i] = C;
}
返回S;
}
INT主（INT ARGC，为const char * argv的[]）
{
//插入code在这里...
性病::法院＆LT;＆LT; getPermutation（4,5）＆其中;＆其中; ENDL;
返回0;
}
发表另一种实现方式哪个更清晰可读，
高清kthperm（S，K）：＃非递归版本
P = []
而S = []！
F =阶乘（LEN（S）-1）
I = INT（楼（K / F））
X = S [i]于
k = k％F
P.append（X）
S = S [我] + S [I + 1：]
返回P
这个问题的语句请求N个元素的第k个排列，在词汇的的排列排序。
在code实现了一个非常漂亮的算法，直接产生第K个置换的元素，为了像这样（伪code）：
GenerateKthPermutation（集合中的元素，诠释K）
{
如果（elements.size（）== 1）
{
输出（elements.getOnlyElement（））;
返回;
}
INT N = elements.size（）;
//有n！元素的排列
//无论我们选择的_first_元素其中之一，有
//将第（n-1）！剩余的元素的排列。
//排列的完整词汇顺序包括：
//第（n-1）！排列开始的最小的元素，然后
//第（n-1）！置换开始的第二小的元素，然后
//第（n-1）！开始的第三最小元素等置换
//所以在（0索引）第k个排列的第一要素，是
//（0索引）地板（K /（N-1）！）个大要素
诠释J =地板（（K-1）/（N-1）！）; // k-1个，由于参数是1索引
// removeJthLargest（0）移除并返回最小的元素
// removeJthLargest（1）移除并返回的第二小
//等等。
输出（elements.removeJthLargest（J））;
//现在输出剩余元素的正确排列。
//我们跳过Ĵ*（N-1）！排列，所以减去给K
的k - = j的*（N-1）;！
//记得元素1小了。
//在现实生活中，你会在这里重复递归代替
GenerateKthPermutation（元素，K）;
}
我希望让事情说清楚。要具体回答你的问题的意见：
原逻辑使用的排序字符串来存储所述一组元素。部分，上面写着通过转移删除ç......就是我说的elements.removeJthLargest（十）的一部分。它消除了正确的元素从字符串并且将其余的做一个新的，规模较小，但仍然排序的字符串。
I am working on below problem and post code I am debugging and the problem statement. Actually I tried to find a few reference solutions, and all are similar without too much explanation. If anyone could help to explain how below logic works, it will be great. I am confused especially by the loop of "for(i=0,k--;i
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 (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Code reference,
#include <iostream>
using namespace std;
string getPermutation(int n, int k) {
int i,j,f=1;
// left part of s is partially formed permutation, right part is the leftover chars.
string s(n,'0');
for(i=1;i<=n;i++){
f*=i;
s[i-1]+=i; // make s become 1234...n
}
for(i=0,k--;i<n;i++){
f/=n-i;
j=i+k/f; // calculate index of char to put at s[i]
char c=s[j];
// remove c by shifting to cover up (adjust the right part).
for(;j>i;j--)
s[j]=s[j-1];
k%=f;
s[i]=c;
}
return s;
}
int main(int argc, const char * argv[])
{
// insert code here...
std::cout << getPermutation(4, 5) << endl;
return 0;
}
Post another implementation which is more clear to read,
def kthperm(S, k): # nonrecursive version
P = []
while S != []:
f = factorial(len(S)-1)
i = int(floor(k/f))
x = S[i]
k = k%f
P.append(x)
S = S[:i] + S[i+1:]
return P
The problem statement asks for the Kth permutation of N elements, in the lexical ordering of the permutations.
The code implements a very nice algorithm that generates the elements of the Kth permutation directly, in order, like this (pseudo-code):
GenerateKthPermutation(Set elements, int k)
{
if (elements.size()==1)
{
output(elements.getOnlyElement());
return;
}
int n = elements.size();
//there are n! permutations of elements
//no matter which one we choose as the _first_ element, there
//will be (n-1)! permutations of the remaining elements.
//The complete lexical ordering of permutations consists of:
//(n-1)! permutations that start with the smallest element, then
//(n-1)! permutations that start with the second smallest element, then
//(n-1)! permutations that start with the 3rd smallest element, etc.
//so the FIRST element in the (0-indexed) kth permutation, is the
//(0-indexed) floor(k/(n-1)!)th-largest element
int j = floor((k-1)/(n-1)!); //k-1, because the parameter is 1-indexed
//removeJthLargest(0) removes and returns the smallest element
//removeJthLargest(1) removes and returns the second-smallest
//etc.
output(elements.removeJthLargest(j));
//now output the correct permutation of remaining elements.
//we've skipped j*(n-1)! permutations, so subtract that from k
k -= j*(n-1)!;
//remember elements is 1 smaller now.
//in real life you would iterate here instead of recursing
GenerateKthPermutation(elements, k);
}
I hope that makes things clear. To specifically answer your question in comments:
The original logic uses a sorted string to store the set of elements. the part that says "remove c by shifting..." is the part where I say "elements.removeJthLargest(j)". It removes the proper element from the string and shifts the remaining ones to make a new, smaller, but still-sorted string.
这篇关于排列顺序的计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
