如何获得N组合R中的第k项
How to get the kth term in N Combination R
如何在 NCR 中获得 kth 组合。无需遍历所有可能的结果。例如假设我有 3C2 个 3 个位置和 2 个相同的项目。我知道它是 [011]、[101] 和 [110]。我怎么得到例如第二项（k=1）是[101]使用的方法？
约束（R < N k >= 0 和 k < P 其中 P = NCR）。
NB:[101] is the 2nd term(in ascending/lexicographical order) because 011 = 3,101 = 5 ,110 = 6
in decimal. so basically the goal is to get what number k in NCR is,
because every kth output from NCR can be represented as a number.
时间复杂度为O(kn)，space为O(n)
public static void main(String[] args) {
//n = 4, r = 2, k = 3
int[] ret1 = getKthPermutation(4, 2, 3);
//ret1 is [1,0,0,1]
//n = 3, r = 2, k = 1
int[] ret2 = getKthPermutation(3, 2, 1);
//ret2 is [1,0,1]
}
static int[] getKthPermutation(int n, int r, int k) {
int[] array = new int[n];
setLastN(array, r, 1);
int lastIndex = n - 1;
for(int count = 0; count < k; count++) {
int indexOfLastOne = findIndexOfLast(array, lastIndex, 1);
int indexOfLastZero = findIndexOfLast(array, indexOfLastOne, 0);
array[indexOfLastOne] = 0;
array[indexOfLastZero] = 1;
//shortcut: swap the part after indexOfLastZero to keep them sorted
int h = indexOfLastZero + 1;
int e = lastIndex;
while(h < e) {
int temp = array[h];
array[h] = array[e];
array[e] = temp;
h++;
e--;
}
}
return array;
}
//starting from `from`, and traveling the array forward, find the first `value` and return its index.
static int findIndexOfLast(int[] array, int from, int value) {
for(int i = from; i > -1; i--)
if(array[i] == value) return i;
return -1;
}
//set the last n elements of an array to `value`
static void setLastN(int[] array, int n, int value){
for(int i = 0, l = array.length - 1; i < n; i++)
array[l - i] = value;
}
这是对非常典型的 "find the kth permation" 算法的改编。
我会尝试解释一下总体思路（你的是一个特例，因为只有两种类型的元素：0 和 1）。
假设我有 [2,1,6,4,7,5]。比当前排列大的下一个最小排列是什么？为什么我关注比当前排列大的下一个最小排列？因为如果您从最小的排列 [1,2,4,5,6,7] 开始并重复该操作（找到比当前大的最小排列）k 次，您将找到第 k+1 个最小的排列。
现在，由于我正在寻找的那个需要比当前的大，我需要增加当前的那个。为了使增量尽可能小，我将尝试修改 5（最后一个）。现在，我不能只将 5 更改为随机值，我只能将它与它前面的某个数字交换。
如果我把 5 和它前面的一个更大的数字交换，比如 7，那么我会得到 [2,1,6,4,5,7]，它比当前的数字小。现在显然我需要将 5 与它前面的一些较小的数字交换，但是哪一个？如果我用 2 交换 5，我得到 [5,1,6,4,7,2]，这个增量太大了。我需要用 "lower digit" 交换 5 以保持增量尽可能小。这导致我们找到小于 5 的第一个（最低）数字（从右到左）。在这种情况下，我需要将 5 与 4 交换并得到 [2,1,6,5,7,4]。这样，我可以使 "swap" 的影响变小。现在前缀确定了[2,1,6,5。没有更小的前缀。我们需要处理后缀7,4]。显然，如果我们对后缀进行排序并使其成为4,7]，那么我们就完成了。
在我们的例子中，有两个区别：
1. 我们需要交换最后一个 1，因为你不能通过将 a 零与其前面的任何数字交换来使排列变大。
2.我们总是可以使用代码中所示的快捷方式对后缀进行排序。我会留给你:)
public static String lexicographicPermutation(String str, long n) {
final long[] factorials = { 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600 };
n--;
char[] arr = str.toCharArray();
for (int i = 0; i < arr.length - 1; i++) {
long fact = factorials[arr.length - i - 2];
long p = i + n / fact;
n %= fact;
for (int j = i + 1; j <= p; j++)
swap(arr, i, j);
}
return new String(arr);
}
private static void swap(char[] arr, int i, int j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
您可以将 STR 替换为所需的字符串。在给定的示例中，1st 排列是 "abcdefghijklm"（这是一个包含 13 个字符的字符串），13!st 排列是反向字符串"mlkjihgfedcba" 和 100st 排列是 "abcfklgmeihjd".
要实现这个解决方案只需 google Factorial number system. This is a key to solve this problem. This is a Project Euler: Problem 24.
演示：
for(int i = 1; i <= 6; i++)
System.out.println(lexicographicPermutation("110", i));
1 - 110
2 - 101
3 - 110
4 - 101
5 - 011
6 - 011
for(int i = 1; i <= 6; i++)
System.out.println(lexicographicPermutation("abc", i));
1 - abc
2 - acb
3 - bac
4 - bca
5 - cab
6 - cba
是的，你说得对：
because every kth output from NCR can be represented as a number.
存在从整数集 1 to # of combs/perms 到整个 combs/perms 集的双射。查找特定 comb/perm 的特定索引有时称为获取排名。根据您在问题中的示例，这些是普通排列。此外，当您提到 升序 时，您指的是 lexicographical order.
计算给定集合的第 nth 个普通排列是一个简单的练习。我们首先需要使用公认的公式获得排列总数：
P(n, r) = n! / (n - r)!
下一部分是关键观察，它使我们能够快速获得目标排列的每个元素。
If we look at all permutations of our set of n choose r, there will be n groups that are only different by a permutation of the n elements.
例如，如果我们查看 第 两组 [0 1 2 3] choose 3 的排列，我们有：
[,0] [,1] [,2]
[0,] 0 1 2
[1,] 0 1 3
[2,] 0 2 1
[3,] 0 2 3
[4,] 0 3 1
[5,] 0 3 2
[6,] 1 0 2
[7,] 1 0 3
[8,] 1 2 0
[9,] 1 2 3
[10,] 1 3 0
[11,] 1 3 2
注意最后的排列只是集合的前6个排列[1 0 2 3]..即0映射到1，1映射到0，最后2个元素映射到自己.
当我们只向右移动而不是 n 个相同的组时，这种模式继续，我们将得到 n - 1 个相似的组第二列，n -2 第三列，依此类推。
所以为了确定我们排列的第一个元素，我们需要确定1st组。我们通过简单地将排列数除以 n 来做到这一点。对于上面 4 选择 3 的排列示例，如果我们正在寻找 15th 排列，我们对第一个元素有以下内容：
Possible indices : [0 1 2 3]
P(4, 3) = 24
24 / 4 = 6 (elements per group)
15 / 6 = 2 (integer division) 2 means the 3rd element here (base zero)
现在我们已经使用了 3rd 元素，我们需要将它从可能的索引数组中删除。我们如何获得下一个元素？
Easy, we get our next subindex by subtracting the product of the group we just found and the elements per group from our original index.
Possible indices : [0 1 3]
Next index is 15 - 6 * 2 = 3
现在，我们重复此操作，直到填满所有条目：
Possible indices : [0 1 3]
Second element
6 / 3 = 2 (elements per group)
3 / 2 = 1
Next index is 3 - 3 * 1 = 0
Possible indices : [0 3]
Third element
2 / 2 = 1
0 / 1 = 0
所以我们的 15th 元素是：[2 1 0]
这是一个 C++ 实现，应该很容易转换为 Java:
double NumPermsNoRep(int n, int k) {
double result = 1;
double i, m = n - k;
for (i = n; i > m; --i)
result *= i;
return result;
}
std::vector<int> nthPermutation(int n, int r, double myIndex) {
int j = 0, n1 = n;
double temp, index1 = myIndex;
std::vector<int> res(r);
temp = NumPermsNoRep(n, r);
std::vector<int> indexVec(n);
std::iota(indexVec.begin(), indexVec.end(), 0);
for (int k = 0; k < r; ++k, --n1) {
temp /= n1;
j = (int) std::trunc(index1 / temp);
res[k] = indexVec[j];
index1 -= (temp * (double) j);
indexVec.erase(indexVec.begin() + j);
}
}
这些概念扩展到其他类型的组合问题，例如找到 nth 组合，或重复排列等。
如何在 NCR 中获得 kth 组合。无需遍历所有可能的结果。例如假设我有 3C2 个 3 个位置和 2 个相同的项目。我知道它是 [011]、[101] 和 [110]。我怎么得到例如第二项（k=1）是[101]使用的方法？
约束（R < N k >= 0 和 k < P 其中 P = NCR）。
NB:
[101]is the 2nd term(in ascending/lexicographical order) because011= 3,101= 5 ,110= 6 in decimal. so basically the goal is to get what number k in NCR is, because every kth output from NCR can be represented as a number.
时间复杂度为O(kn)，space为O(n)
public static void main(String[] args) {
//n = 4, r = 2, k = 3
int[] ret1 = getKthPermutation(4, 2, 3);
//ret1 is [1,0,0,1]
//n = 3, r = 2, k = 1
int[] ret2 = getKthPermutation(3, 2, 1);
//ret2 is [1,0,1]
}
static int[] getKthPermutation(int n, int r, int k) {
int[] array = new int[n];
setLastN(array, r, 1);
int lastIndex = n - 1;
for(int count = 0; count < k; count++) {
int indexOfLastOne = findIndexOfLast(array, lastIndex, 1);
int indexOfLastZero = findIndexOfLast(array, indexOfLastOne, 0);
array[indexOfLastOne] = 0;
array[indexOfLastZero] = 1;
//shortcut: swap the part after indexOfLastZero to keep them sorted
int h = indexOfLastZero + 1;
int e = lastIndex;
while(h < e) {
int temp = array[h];
array[h] = array[e];
array[e] = temp;
h++;
e--;
}
}
return array;
}
//starting from `from`, and traveling the array forward, find the first `value` and return its index.
static int findIndexOfLast(int[] array, int from, int value) {
for(int i = from; i > -1; i--)
if(array[i] == value) return i;
return -1;
}
//set the last n elements of an array to `value`
static void setLastN(int[] array, int n, int value){
for(int i = 0, l = array.length - 1; i < n; i++)
array[l - i] = value;
}
这是对非常典型的 "find the kth permation" 算法的改编。
我会尝试解释一下总体思路（你的是一个特例，因为只有两种类型的元素：0 和 1）。
假设我有 [2,1,6,4,7,5]。比当前排列大的下一个最小排列是什么？为什么我关注比当前排列大的下一个最小排列？因为如果您从最小的排列 [1,2,4,5,6,7] 开始并重复该操作（找到比当前大的最小排列）k 次，您将找到第 k+1 个最小的排列。
现在，由于我正在寻找的那个需要比当前的大，我需要增加当前的那个。为了使增量尽可能小，我将尝试修改 5（最后一个）。现在，我不能只将 5 更改为随机值，我只能将它与它前面的某个数字交换。
如果我把 5 和它前面的一个更大的数字交换，比如 7，那么我会得到 [2,1,6,4,5,7]，它比当前的数字小。现在显然我需要将 5 与它前面的一些较小的数字交换，但是哪一个？如果我用 2 交换 5，我得到 [5,1,6,4,7,2]，这个增量太大了。我需要用 "lower digit" 交换 5 以保持增量尽可能小。这导致我们找到小于 5 的第一个（最低）数字（从右到左）。在这种情况下，我需要将 5 与 4 交换并得到 [2,1,6,5,7,4]。这样，我可以使 "swap" 的影响变小。现在前缀确定了[2,1,6,5。没有更小的前缀。我们需要处理后缀7,4]。显然，如果我们对后缀进行排序并使其成为4,7]，那么我们就完成了。
在我们的例子中，有两个区别： 1. 我们需要交换最后一个 1，因为你不能通过将 a 零与其前面的任何数字交换来使排列变大。 2.我们总是可以使用代码中所示的快捷方式对后缀进行排序。我会留给你:)
public static String lexicographicPermutation(String str, long n) {
final long[] factorials = { 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600 };
n--;
char[] arr = str.toCharArray();
for (int i = 0; i < arr.length - 1; i++) {
long fact = factorials[arr.length - i - 2];
long p = i + n / fact;
n %= fact;
for (int j = i + 1; j <= p; j++)
swap(arr, i, j);
}
return new String(arr);
}
private static void swap(char[] arr, int i, int j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
您可以将 STR 替换为所需的字符串。在给定的示例中，1st 排列是 "abcdefghijklm"（这是一个包含 13 个字符的字符串），13!st 排列是反向字符串"mlkjihgfedcba" 和 100st 排列是 "abcfklgmeihjd".
要实现这个解决方案只需 google Factorial number system. This is a key to solve this problem. This is a Project Euler: Problem 24.
演示：
for(int i = 1; i <= 6; i++)
System.out.println(lexicographicPermutation("110", i));
1 - 110
2 - 101
3 - 110
4 - 101
5 - 011
6 - 011
for(int i = 1; i <= 6; i++)
System.out.println(lexicographicPermutation("abc", i));
1 - abc
2 - acb
3 - bac
4 - bca
5 - cab
6 - cba
是的，你说得对：
because every kth output from NCR can be represented as a number.
存在从整数集 1 to # of combs/perms 到整个 combs/perms 集的双射。查找特定 comb/perm 的特定索引有时称为获取排名。根据您在问题中的示例，这些是普通排列。此外，当您提到 升序 时，您指的是 lexicographical order.
计算给定集合的第 nth 个普通排列是一个简单的练习。我们首先需要使用公认的公式获得排列总数：
P(n, r) = n! / (n - r)!
下一部分是关键观察，它使我们能够快速获得目标排列的每个元素。
If we look at all permutations of our set of n choose r, there will be n groups that are only different by a permutation of the n elements.
例如，如果我们查看 第 两组 [0 1 2 3] choose 3 的排列，我们有：
[,0] [,1] [,2]
[0,] 0 1 2
[1,] 0 1 3
[2,] 0 2 1
[3,] 0 2 3
[4,] 0 3 1
[5,] 0 3 2
[6,] 1 0 2
[7,] 1 0 3
[8,] 1 2 0
[9,] 1 2 3
[10,] 1 3 0
[11,] 1 3 2
注意最后的排列只是集合的前6个排列[1 0 2 3]..即0映射到1，1映射到0，最后2个元素映射到自己.
当我们只向右移动而不是 n 个相同的组时，这种模式继续，我们将得到 n - 1 个相似的组第二列，n -2 第三列，依此类推。
所以为了确定我们排列的第一个元素，我们需要确定1st组。我们通过简单地将排列数除以 n 来做到这一点。对于上面 4 选择 3 的排列示例，如果我们正在寻找 15th 排列，我们对第一个元素有以下内容：
Possible indices : [0 1 2 3]
P(4, 3) = 24
24 / 4 = 6 (elements per group)
15 / 6 = 2 (integer division) 2 means the 3rd element here (base zero)
现在我们已经使用了 3rd 元素，我们需要将它从可能的索引数组中删除。我们如何获得下一个元素？
Easy, we get our next subindex by subtracting the product of the group we just found and the elements per group from our original index.
Possible indices : [0 1 3]
Next index is 15 - 6 * 2 = 3
现在，我们重复此操作，直到填满所有条目：
Possible indices : [0 1 3]
Second element
6 / 3 = 2 (elements per group)
3 / 2 = 1
Next index is 3 - 3 * 1 = 0
Possible indices : [0 3]
Third element
2 / 2 = 1
0 / 1 = 0
所以我们的 15th 元素是：[2 1 0]
这是一个 C++ 实现，应该很容易转换为 Java:
double NumPermsNoRep(int n, int k) {
double result = 1;
double i, m = n - k;
for (i = n; i > m; --i)
result *= i;
return result;
}
std::vector<int> nthPermutation(int n, int r, double myIndex) {
int j = 0, n1 = n;
double temp, index1 = myIndex;
std::vector<int> res(r);
temp = NumPermsNoRep(n, r);
std::vector<int> indexVec(n);
std::iota(indexVec.begin(), indexVec.end(), 0);
for (int k = 0; k < r; ++k, --n1) {
temp /= n1;
j = (int) std::trunc(index1 / temp);
res[k] = indexVec[j];
index1 -= (temp * (double) j);
indexVec.erase(indexVec.begin() + j);
}
}
这些概念扩展到其他类型的组合问题，例如找到 nth 组合，或重复排列等。