algorithm - 具有重复字符的字符串排列

Question

我有字符串“0011”并且希望所有组合都没有重复。这意味着我想要一个由两个“0”和两个“1”组合而成的字符串；例如:[0011,0101,0110,1001,1010,1100]

我试过这个，结果正是我需要的。

private void permutation(String result, String str, HashSet hashset) {
        if (str.length()==0 && !hashSet.contains(result)){
            System.out.println(result);
            hashSet.add(result);
            return;
        }
        IntStream.range(0,str.length()).forEach(pos->permutation(result+ str.charAt(pos), str.substring(0, pos) + str.substring(pos+1),hashset));
    }

如果我删除 HashSet，此代码将产生 24 个结果而不是 6 个结果。

但是这段代码的时间复杂度是O(n!)。
如何避免创建重复字符串并降低时间复杂度？

Answer 1

可能这样的东西比 n!即使在小 n这个想法是计算结果项中我们需要多少位，并且遍历所有可能的值并仅过滤那些具有相同位数的值。只有一个 1 和 50%/50% 的 0 和 1 时，它将工作相似的时间

function bitCount(n) {
        n = n - ((n >> 1) & 0x55555555)
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
        return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
    }
    function perm(inp) {
        const bitString = 2;
        const len = inp.length;
        const target = bitCount(parseInt(inp, bitString));
        const min = (Math.pow(target, bitString) - 1);
        const max = min << (len - target);
        const result = [];
        for (let i = min; i < max + 1; i++) {
            if (bitCount(i) === target) {
                result.push(i.toString(bitString).padStart(len, '0'));
            }
        }
        return result;
    }
    
     const inp = '0011';
     const res = perm(inp);
     console.log('result',res);

附言我的第一个想法可能比上层代码更快。但是upper更容易实现

第一个想法是将字符串转换为整数并使用按位左移，但每次只使用一个数字。它仍然取决于n。并且可以大于或小于上面的解决方案。但位移本身更快。

example 
const input = '0011'
const len = input.length;

step1: calc number of bits = 2;
then generate first element = 3(Dec) is = '0011' in bin
step2 move last from the right bit one position left with << operator: '0101'
step3 move again: '1001'
step4: we are reached `len` so use next bit:100'1' : '1010'
step5: repeat:'1100'
step6: move initial 3 << 1: '0110'
repeat above steps: '1010'
step8: '1100'
it will generate duplicates so probably can be improved

希望对你有帮助