Алгоритм перестановки для n символов в x позициях

Question

Например, алгоритм перестановки для {&, *,%} должен быть размещен в 8 позициях:

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

...

Алгоритм перестановки кучи, который я видел в Интернете, работает только для теху кого количество символов равно количеству позиций, а у тех, кто может работать с неравным количеством символов и количеством позиций, работают только целые числа, а не символы.Я также должен сказать, что до сих пор не достиг ни одного рабочего алгоритма, так как я ничего не знаю об алгоритмах.У меня была одна попытка, которую я не смог назвать алгоритмом после того, как увидел алгоритм кучи!Если это помогает:

1. Добавить & к выходному массиву.
2. Добавить % к выходному массиву по новому индексу.
3. Добавить * в выходной массив с новым индексом.
4. Выполните рекурсивный алгоритм для каждых трех.

Но я, очевидно, не могу обрабатывать индексы массива.Я также пытался использовать числа от 0 до 2 для &,%, *;Но я не нашел хорошего ответа.

Answer 1

Вы можете использовать стандартный метод одометра ( 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>
%%%%%%**
%%%%%%*%
%%%%%%%&
%%%%%%%*
%%%%%%%%

Answer 2

Перестановки могут быть перечислены путем подсчета базы 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
# /1983393/python-elegantnaya-obratnaya-funktsiya-ot-int-string-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