x位置n个字符的排列算法

Question

例如{&, *, %} 8个位置的排列算法：

&&&&&&&&&
&&&&&&&&*
&&&&&&&&%
&&&&&&&*%
&&&&&&&**

...

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

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

但我显然无法处理数组索引。我也尝试过使用 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
# 
#
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

您可以使用标准 "odometer" 方法 (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>
%%%%%%**
%%%%%%*%
%%%%%%%&
%%%%%%%*
%%%%%%%%

x位置n个字符的排列算法

Permutation algorithm for n characters in x positions

arrays

algorithm

permutation

heaps-algorithm

算法（伪代码）

代码示例（在 Python 中）

实例（repl.it）