0

Let's say I have a row filled with three different strings in different cells, how do I create a permutation algorithm that will generate the following outputs?

Input: Cat Dog Rat

Ouput:

Cat Dog Rat

Cat Rat Dog

Dog Cat Rat

Dog Rat Cat

Rat Dog Cat

Rat Cat Dog

Most of the solutions in the web generate combinations instead of the desired permutations. Also, the solutions I found involved strings in just one cell. i.e.: Cat --> Cat, Cta, Atc, Act, etc etc etc

I hope someone could help me out a bit regarding this - or at least provide a starting point.

Many thanks in advance!

Nate
  • 1
  • There're many string versions you can find on the interwebs where you can exchange a string for a `String[]` or better `List` and change it to index the entire element as opposed to the character and your ready to go. Many *do* do the permutations correctly. – ChiefTwoPencils Mar 30 '15 at 03:11
  • This is a typical recursion problem, there're many ways to solve it. Assuming this is an assignment, i will give you a tip and let you try to do the rest. Assume f(array, count, prefixArray) is a function that output permutations of "array" of length "count", and attach prefixArray's items in the front of each output. Try to identify the base case and solve it, and then find a way to solve f(array, n, prefixArray) using f(array, n-1, prefixArray) – JK ABC Mar 30 '15 at 03:14

1 Answers1

0

1) Define your tokens, a token will be a string unit (Cat, Dog and Rat each is a token), assign a number to each, 0 1 2 will work since they'll probably go to an array.

2) nest for loops??? for(i=0 to 2) for(j=0 to 2) for(k=0 to 2) return arr[i]+arr[j]+arr[k]

gia
  • 757
  • 5
  • 19