-6

I need to make a program that use recursion with a loop to show every permutaion. let say if input is "abc" output:

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

but i am still able to show (abc, acb, bac, bca, cab, cba) Can anyone suggest any algorithm. (C++ preferred)

10
  • Share what you got so far, i mean the code, then we can help you. Sep 28, 2018 at 14:46
  • 3
    "a" is not a permutation of "abc"
    – Slava
    Sep 28, 2018 at 14:51
  • 1
    The C++ standard library has next_permutation. Does this do what you want?
    – Paul Floyd
    Sep 28, 2018 at 14:56
  • @PaulFloyd. i need to make all possible outputs. next_permutation will give abc, acb, bac, bca, cab, cba but how can get others Sep 28, 2018 at 15:05
  • @Black_Raven. My code is working to show abc, acb, bac, bca, cab, cba Sep 28, 2018 at 15:07

1 Answer 1

1

You want all permutations of each member of the powerset of the input.

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

Where input[i..j] represents the sub string of input from i(inclusive) to j(exclusive), and + is string concatenation.

Note that this will include the empty set, which strictly speaking is correct, but you didn't include it.

Here's the original Java implementation and my conversion to C++, which you should not trust :)

1
  • It's pseudocode. I've added a link to a Java implementation. Sep 28, 2018 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.