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

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);

附：我的第一个想法可能比上面的代码更快。但鞋帮更容易实施

第一个想法是将字符串转换为int并使用按位左移，但每次只使用一位数。它仍然取决于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

希望能帮助到你

Answer 2

由于字符串中不存在重复，因此无法改善最坏情况下的时间复杂度。但是，在多集的情况下，我们可以修剪很多子树以防止重复。

关键的想法是使用传统的回溯算法来置换字符串，但如果先前已交换字符以防止重复，则可以防止交换。

这是一个C ++代码片段，可以防止重复，并且不使用任何内存进行查找。

bool shouldSwap(const string& str, size_t start, size_t index) {
  for (auto i = start; i < index; ++i) {
    if (str[i] == str[index])
      return false;
  }
  return true;
}

void permute(string& str, size_t index)
{
  if (index >= str.size()) {
    cout << str << endl;;
    return;
  }

  for (size_t i = index; i < str.size(); ++i) {
    if(shouldSwap(str, index, i)) {
      swap(str[index], str[i]);
      permute(str, index + 1);
      swap(str[index], str[i]);
    }
  }
}

运行demo。另请参阅SO答案here和Distinct permutations以获取更多参考资料。

另请注意，此解决方案的时间复杂度为O（n2 n！）

• O（n）用于打印字符串
• O（n）用于迭代字符串以生成交换和重复。
• O（n！）个排列数的可能状态。