arrays - x位置中n个字符的置换算法

Question

例如 {&, *, %} 的置换算法被放置在 8 个位置：

1. &&&&&&&&&
2. &&&&&&&&*
3. &&&&&&&&%
4. &&&&&&&*%
5. &&&&&&&**

...

我在网上看到的堆的排列算法只适用于字符数等于位置数的那些，而那些可以使用不等字符数和位置数的那些，仅适用于整数，而不适用于字符。我还不得不说到目前为止我还没有达到任何工作算法，因为我对算法一无所知。我试了一次，看到堆的算法后，我无法命名它的算法！如果有帮助：

1. 添加&到输出数组。
2. 添加%到新索引上的输出数组。
3. 添加*到新索引上的输出数组。
4. 对每三个做一个递归算法。

但我显然无法处理数组索引。我也尝试使用从 0 到 2 的数字来表示 &、%、*; 但我没有得到一个好的答案。

Answer 1

排列可以通过计数基数 3 列出。

• & = 0
• * = 1
• % = 2

算法（伪代码）

Start i=00000000 and end at 22222222 in base 3:
    str_i = encode i in { &, *, % } character set
    print str_i
    i = i + 1 (in base 3)

代码示例（在 Python 中）

def main():
  start = int('00000000', 3)
  end = int('22222222', 3)
  for i in range(start, end + 1):
    # convert binary to base 3
    perm_base3 = str_base(i, 3)
    perm_charset = encode_to_charset(perm_base3)
    print(perm_charset)

# custom character set
# & = 0
# * = 1
# % = 2
def encode_to_charset(str_number_base3):
  ret = []
  for c in str_number_base3:
    if c == '0':
      ret.append('&')
    elif c == '1':
      ret.append('*')
    elif c == '2':
      ret.append('%')
    else:
      pass #TODO handle error here
  return "".join(ret)

#
# Utility functions
# https://stackoverflow.com/questions/2063425/python-elegant-inverse-function-of-intstring-base
#
def digit_to_char(digit):
    if digit < 10: return chr(ord('0') + digit)
    else: return chr(ord('a') + digit - 10)

def str_base(number,base):
    if number < 0:
        return '-' + str_base(-number,base)
    else:
        (d,m) = divmod(number,base)
        if d:
            return str_base(d,base) + digit_to_char(m)
        else:
            return digit_to_char(m)

main()

现场示例（在 repl.it 上）

https://repl.it/@KyleMarshall1/PermutationAlgorithm

Answer 2

您可以使用标准的“里程表”方法（IDEOne）：

static void permute(String str, int len)
{    
  char[] chars = str.toCharArray();

  int[] idx = new int[len];

  char[] perm = new char[len];    
  Arrays.fill(perm, chars[0]);

  while(true)
  {      
    System.out.println(new String(perm));

    int k=idx.length-1;
    for(; k>=0; k--)
    {
      idx[k] += 1;
      if(idx[k] < chars.length) 
      {
        perm[k] = chars[idx[k]];
        break;
      }
      idx[k] = 0;
      perm[k] = chars[idx[k]];
    }
    if(k < 0) break;
  }
}

测试：

public static void main(String[] args)
{
  permute("&*%", 8);
}

输出：

&&&&&&&&
&&&&&&&*
&&&&&&&%
&&&&&&*&
&&&&&&**
&&&&&&*%
&&&&&&%&
&&&&&&%*
&&&&&&%%
&&&&&*&&
<snip>
%%%%%%**
%%%%%%*%
%%%%%%%&
%%%%%%%*
%%%%%%%%