0

I am writing code to calculate all the permutations of a list and for the sake of optimization, would like to find an algorithm which generates permutations without changing the first and last element of my set.

eg: {0,1,2,3,4} {0,1,3,2,4} {0,2,1,3,4} {0,2,3,1,4} {0,3,2,1,4} {0,3,1,2,4}

Currently I am using heap's algorithm on the center elements and for each permutation I have to re-add the first and last element after. This seems inefficient to me. Any advice?

Christian Nebe
  • 1
  • The idea that it is inefficient to "add" first and last elements after generating the bulk of a permutation strikes me as dependent on the representation of these permutations as well as (perhaps) the programming language used. It would give your Question more context if such details were sketched for the sake of discussion. – hardmath May 25 '19 at 02:58

1 Answers1

0

You could keep the first and last element where they are but apply Heap's algorithm to the middle, and ignore the first and last element in the algorithm.

auscrypt
  • 8,186
  • Any idea of how to do that? – Christian Nebe May 25 '19 at 03:47
  • Um, what's that supposed to mean? I just explained how to do it. If you mean the actual implementation of the code, then math.stackexchange is not the right place to ask. – auscrypt May 25 '19 at 03:51
  • Again this is very dependent on the programming language you use and the data structure you use. If you're doing this in C with an array, for example, you would be passing a pointer into the permutation function, so just pass p + 1 to your function instead of p in order to skip over the first element of the array; and of course the number of elements to give to the function is n - 2 if the actual array has n elements. If you're working in a language where you can't so easily fake the start of the array, you might actually have to change the indexing inside the function. – David K May 25 '19 at 15:51