Алгоритм (особенно для c ++), чтобы показать каждую перестановку

Question

Мне нужно сделать программу, которая использует рекурсию с циклом для отображения каждой перестановки .скажем, если вход «abc»:

a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
cb
cba
ca
cab

, но я все еще могу показать (abc, acb, bac, bca, cab, cba) Может кто-нибудь предложить любой алгоритм ,(Предпочтительно C ++)

Answer 1

Вы хотите, чтобы все перестановки каждого члена powerset входа.

permSub("abc", "")

func permSub(input, perm)
  print perm
  if input = "" return

  for i = 0 to input.length-1
    permSub(input[0..i]+input[i+1..input.length), perm+input[i]
  end
end

Где input[i..j] представляет подстроку input от i(inclusive) до j(exclusive), а + - конкатенацию строк.

Обратите внимание, что это будет включатьпустой набор, который, строго говоря, является правильным, но вы его не включили.

Вот оригинальная реализация Java и мое преобразование в C ++, что вам не следуетдоверие:)