获取组合中的偏移量而不生成所有可能的组合 [英] Get offset in combinations without generating all possible combinations

问题描述

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

I'm trying to get a specific combination from all possible combinations of a 6 character combination with any characters a-z,0-9. There are a few hundred million possible combinations and I can find the offset when generating the combinations through recursion but I would much rather use an algorithm that doesn't need to store all preceding combinations to arrive at the given offset. I'm not a math guy and I figure this is pretty mathie. Any advice would be greatly appreciated... Thanks

我发现了以下问题:查找特定组合的索引，而不生成所有ncr组合

..但是我不擅长C#，并且不确定是否可以将其正确转换为PHP.

.. but I'm not adept at C# and not sure if I can correctly translate it to PHP.

推荐答案

我不是PHP专家，但是希望没有高级魔术的JavaScript代码可以成为我们的共同点.所以首先这里是一些代码:

I'm not a PHP-guy but hopefully a JavaScript code with no advanced magic could be our common ground. So first here is some code:

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来更改它.

Obviously if order of digits and letters is different for you, you can change it by either passing explicitly chars (last argument) or changing defaultChars.

背后的一些数学运算

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

For permutations you may see a string as a number written in a 36-base numeral system (36 = 10 digits + 26 letters) similar to how hexadecimal works. So converting index <=> permutation is actually a simple job of converting to and from that numeral system.

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

For combinations idea is similar but the numeral system is what I call a "variable-base" numeral system with base changing from 36 to 36-n+1 (where n is the target length of combination). An example of a more familiar "variable-base" numeral system is clock. If you want to convert milliseconds into time, you first divide by 1000 milliseconds, then by 60 seconds, then by 60 minutes, and then by 24 hours. The only really trick part here is that which "digits" are allowed for each position depends on which digits are already used by the previous positions (size of the digits set is always the same nevertheless). This tricky part is the reason chars argument is modified to remove one char after each iteration in both combinationToIndex and indexToCombination.

这篇关于获取组合中的偏移量而不生成所有可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！