在组合中获取偏移量，而不生成所有可能的组合

Question

我正在尝试从 6 个字符组合与任何字符 a-z，0-9 的所有可能组合中获取特定组合。有几亿种可能的组合，在通过递归生成组合时，我可以找到偏移量，但我宁愿使用一种不需要存储所有先前组合来达到给定偏移量的算法。我不是一个数学家，我认为这很数学。任何建议将不胜感激...谢谢

我发现了这个问题：在不生成所有 ncr 组合的情况下查找特定组合的索引

.. 但我不擅长 C#，不确定我是否可以正确地将其翻译成 PHP。

Answer 1

我不是PHP人，但希望没有高级魔法的JavaScript代码可以成为我们的共同点。所以首先这里有一些代码：

const defaultChars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
function indexToPermutation(index, targetLength, chars) {
if (arguments.length < 3)
chars = defaultChars;
const charsLen = chars.length;
let combinationChars = [];
for (let i = 0; i < targetLength; i++) {
let ch = chars[index % charsLen];
combinationChars.push(ch);
index = Math.floor(index / charsLen); //integer division
}
return combinationChars.reverse().join("")
}
function permutationToIndex(combination, chars) {
if (arguments.length < 2)
chars = defaultChars;
const charsLen = chars.length;
let index = 0;
let combinationChars = combination.split("");
for (let i = 0; i < combination.length; i++) {
let digit = chars.indexOf(combinationChars[i]);
index = index * charsLen + digit;
}
return index;
}

function indexToCombination(index, targetLength, chars) {
if (arguments.length < 3)
chars = defaultChars;
let base = chars.length - targetLength + 1;
let combinationIndices = [];
for (let i = 0; i < targetLength; i++) {
let digit = index % base;
combinationIndices.push(digit);
index = Math.floor(index / base); //integer division
base++;
}
let combinationChars = [];
for (let i = targetLength - 1; i >= 0; i--) {
let ch = chars[combinationIndices[i]];
combinationChars.push(ch);
// here it is important that chars is only local copy rather than global variable
chars = chars.slice(0, combinationIndices[i]) + chars.slice(combinationIndices[i] + 1);  // effectively chars.removeAt(combinationIndices[i])
}
return combinationChars.join("")
}
function combinationToIndex(combination, chars) {
if (arguments.length < 2)
chars = defaultChars;
const charLength = chars.length; // full length before removing!
let combinationChars = combination.split("");
let digits = [];
for (let i = 0; i < combination.length; i++) {
let digit = chars.indexOf(combinationChars[i]);
// here it is important that chars is only local copy rather than global variable
chars = chars.slice(0, digit) + chars.slice(digit + 1); // effectively chars.removeAt(digit)
digits.push(digit);
}
let index = 0;
let base = charLength;
for (let i = 0; i < combination.length; i++) {
index = index * base + digits[i];
base--;
}
return index;
}

这里有一些结果

indexToPermutation(0, 6) => "000000"
indexToPermutation(1, 6) => "000001"
indexToPermutation(123, 6) => "00003F"
permutationToIndex("00003F") => 123
permutationToIndex("000123") => 1371
indexToCombination(0,6) => "012345"
indexToCombination(1,6) => "012346"
indexToCombination(123,6) => "01237Z"
combinationToIndex("01237Z") => 123
combinationToIndex("543210") => 199331519

显然，如果数字和字母的顺序对您来说不同，您可以通过显式传递chars(最后一个参数)或更改defaultChars来更改它。

它背后的一些数学

对于排列，您可能会看到字符串作为以36基数系统(36= 10 位数字 + 26 个字母)书写的数字，类似于十六进制的工作方式。因此，转换索引 <=> 排列实际上是与该数字系统之间的简单工作。

对于组合，想法是相似的，但数字系统是我所说的"可变基数"数字系统，其基数从36变为36-n+1(其中n是组合的目标长度)。更熟悉的"可变基数"数字系统的一个例子是时钟。如果要将毫秒转换为时间，请先除以 1000 毫秒，然后除以 60 秒，然后除以 60 分钟，然后除以 24 小时。这里唯一真正棘手的部分是，每个位置允许哪些"数字"取决于先前的位置已经使用了哪些数字(尽管如此，数字集的大小总是相同的)。这个棘手的部分是修改参数以在combinationToIndex和indexToCombination中每次迭代后删除一个字符chars的原因。