🔒 Locked

algorithm for finding all permutations

Started by AndreTheGiant May 7, 2004 at 10:09 PM 1 replies 300+ views

Original Post

AndreTheGiant

179

AndreTheGiant

May 7, 2004 at 10:09 PM

Suppose you have a programming problem where you need to ''try every possibility''. This is often reduced to trying all permutations of something. Permutations is a simple concept, but I cant think of an algorithm for it. For example, suppose you have these numbers in an array: 1 2 3 4 What would be an alg to produce all permutations? For eg: 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

Aprosenf

May 7, 2004 at 10:19 PM

#include <algorithm>


int array[4] = {1, 2, 3, 4};


cout << array[0] << ' ' << array[1] << ' ' << array[2] << ' ' << array[3] << endl;


for(int i = 0; i < 24; i++)
{
	std::next_permutation(array, array + 4);


	cout << array[0] << ' ' << array[1] << ' ' << array[2] << ' ' << array[3] << endl;
}

[edited by - aprosenf on May 7, 2004 11:20:31 PM]

SiCrane

Mod

473

SiCrane

May 7, 2004 at 10:20 PM

Well the C++ answer is to just use std:next_permutation().

However, to actually answer your question, the easiest method to grasp this conceptually is, IMO, recursion. Let''s say you have a set that you want to find all the permutations for. Take all the elements of the set one at a time, and consider the permutations of the remaining elements. In pseudo-code it might look like:


set FindPermutations(set input)
  if |input| = 1
    return input
  else 
    set return_values = {}
    foreach element e in input
      subset = input - e
      subset_permutations = FindPermutations(subset)
      foreach element p in subset_permutations
        return_values += p.prepend(e)
    return return_values

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.