6
$\begingroup$

This question already has an answer here:

Does anyone know of a replacement for NextPermutation in Combinatorica? The problem with loading Combinatorica is that it interferes with new functionality which I also want to use. I need to generate all the permutations of a list in lexicographic order one by one. Thanks for your help.

$\endgroup$

marked as duplicate by J. M. will be back soon Nov 15 at 17:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ If you want all permutations in canonical order just use Permutations For perm = Permutations[{a, b, c, d, e, f, g}]; then OrderedQ[perm] evaluates to True $\endgroup$ – Bob Hanlon Oct 6 at 15:11
  • 2
    $\begingroup$ @BobHanlon The problem with this approach is that you get all the permutations at once in memory, which I want to avoid ... I want to access them one by one, else there are too many ... there are close to 40 M permutations with lists that have 11 members, too many to have in memory, but it is possible with some time to look at each one of them and seek the property I want ... does this make sense? $\endgroup$ – EGME Oct 6 at 15:17
  • $\begingroup$ Can you explain more about what do you need to do? (Not all people here might be familiar with the Combinatorica package). $\endgroup$ – TumbiSapichu Oct 6 at 15:33
  • $\begingroup$ @TumbiSapichu Right: I would like to access each and all of the permutations of a list, one at a time. A function like Permutations that returns all the permutations is of no use, given the large number of permutations that I need to inspect. The logical way make sure you access each and every permutation is to do so in some order, say, the lexicographic order. Does this make sense? So the function NextPermutation applied to the list {1,2,3} would return {1,3,2} ... essentially I want a function that implements this ... it used to exist, in the Combinatorica package ... contd. $\endgroup$ – EGME Oct 6 at 15:38
  • $\begingroup$ @TumbiSapichu The problem with loading Combinatorica is that it overlaps with functionality that has replaced some of what is in there ... $\endgroup$ – EGME Oct 6 at 15:38
8
$\begingroup$

See page 57 of the book Computational Discrete Mathematics by Pemmaraju and Skiena.

NextPermutation[l_List] := Sort[l] /; (l === Reverse[Sort[l]])

NextPermutation[l_List] :=
   Module[{n = Length[l], i, j, t, nl = l},
      i = n - 1;
      While[Order[nl[[i]], nl[[i + 1]]] == -1, i--];
      j = n;
      While[Order[nl[[j]], nl[[i]]] == 1, j--];
      {nl[[i]], nl[[j]]} = {nl[[j]], nl[[i]]};
      Join[Take[nl, i], Reverse[Drop[nl, i]]]
   ]

For example:

NextPermutation[{8, 7, 6, 5, 4, 3, 2, 1}]

{1, 2, 3, 4, 5, 6, 7, 8}

NextPermutation[{7, 12, 4, 1, 3, 10, 5, 6, 8, 11, 2, 9}]

{7, 12, 4, 1, 3, 10, 5, 6, 8, 11, 9, 2}

$\endgroup$
  • $\begingroup$ Thank you, this is quite useful, not having the book - even if ideally, I want a “plug and play” replacement which is as fast as possible - thanks once again! $\endgroup$ – EGME Oct 7 at 7:38
  • $\begingroup$ I should accept one of the two answers if nothing else comes, the problem is choosing one of the two! $\endgroup$ – EGME Oct 7 at 7:39
  • 2
    $\begingroup$ Just as an extra remark: if you change the instances such as Order[x, y] == 1 (which doesn't compile) with OrderedQ[{x, y}] (which does), you can plonk the whole thing into Compile and get a much faster version for integers. $\endgroup$ – Sjoerd Smit Oct 7 at 11:21
6
$\begingroup$

The best way for me to do what you are asking for is to, if I remember correctly from the last time I did something like this.

  1. Open up Combinatorica.m in a fresh notebook. It contains what looks like Mathematica code and Mathematica is happy to do this. The last time I looked the Combinatorica.m file is still there buried down inside the installed Mathematica files. Try searching your entire file system for the name if you can't find it.

  2. Scroll down and find the well written self contained definition of NextPermutation

  3. Scrape that definition into your clipboard

  4. Close the notebook without changing Combinatorica.m

  5. Open up your notebook

  6. Paste the definition into your notebook, along with credits, where it came from and how to find it and do this again if you need to

and you are ready to go with your own personal copy of NextPermutation in your notebook without any of the other definitions from combinatorica.m

$\endgroup$
  • $\begingroup$ Thank you, this is also quite useful ... I haven’t tried it, but I think I will try it ... it solves a more general problem, and it is almost like plug and play, although this is not as optimized as might be ... as in the answer above, I would accept one of the two answers, were it not difficult to choose one, and waiting also for something else that might come around $\endgroup$ – EGME Oct 7 at 7:41
  • $\begingroup$ Note that FindFile["Combinatorica`"] gives a hint where to look for the file. $\endgroup$ – Michael E2 Oct 7 at 13:22
  • $\begingroup$ @EGME I don't assume that readers have a copy of "Computational Discrete Mathematics" on their shelves, although I've recommended that in the past. It seems more and more when I recommend looking in a book that the response is "Oh GAWD! Not a dead tree! Can't you just tell me where I can scrape the code." I'm not kidding, I've gotten that response from people. $\endgroup$ – Bill Oct 8 at 15:28
  • $\begingroup$ @Bill Right ... I use libraries, or look for electronic copies of books ... many books now exist in electronic form ... maybe this one does, and I just didn’t look well enough. ... this one really seems like a book that ought to be in a shelf as you say, classics are worth getting even if in print, I think. $\endgroup$ – EGME Oct 8 at 15:51
2
$\begingroup$

If you have a numeric list, we can get a substantial speedup by using Compile.

nextPerm = Compile[{{operm, _Integer, 1}},
  Module[{i, j, perm},
    perm = operm;
    j = Length[perm];
    i = j-1;
    While[i > 0 && perm[[i]] > perm[[i+1]], i--];
    If[i == 0, Return[Reverse[perm]]];
    While[perm[[j]] < perm[[i]], j--];
    perm[[{i, j}]] = perm[[{j, i}]];
    Join[perm[[1 ;; i]], perm[[-1 ;; i+1 ;; -1]]]
  ],
  CompilationTarget -> "C",
  RuntimeOptions -> "Speed"
];

Cycling through all permutations:

Nest[nextPerm, Range[11], 11!] // AbsoluteTiming
{29.7751, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}}

Compare to Combinatorica:

<<Combinatorica`
Nest[NextPermutation, Range[11], 11!] // AbsoluteTiming
{637.568, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}}
$\endgroup$
  • $\begingroup$ Thank you ... this is indeed quite useful ... very significant speed up ... $\endgroup$ – EGME Oct 7 at 14:42
1
$\begingroup$

If you ever need a definition from an old function like this, you can try this trick to see if you can access the definition of the function directly:

<<Combinatorica`
GeneralUtilities`PrintDefinitions[NextPermutation]
$\endgroup$
  • $\begingroup$ The source code of Combinatorica is available. It's better to read the source file, in case there are any comments. $\endgroup$ – Szabolcs Oct 7 at 11:21
0
$\begingroup$

I have made use of commands from Combinatorica as well as more recent built-in commands, in the same code, and where their names have clashed, I have tried to differentiate between them by referring to them as, for example,

Combinatorica`SymmetricGroup

for the Combinatorica one, and

System`SymmetricGroup

for the more recent one, rather than just SymmetricGroup. This seems to have worked for me.

$\endgroup$
  • 1
    $\begingroup$ I'd be curious to know what it is that you need from Combinatorica that you cannot get elsewhere. $\endgroup$ – Szabolcs Oct 7 at 11:22
  • 2
    $\begingroup$ SetPartitions and RankSetPartition were two examples, I seem to remember, and I think that for some reason I preferred the Combinatorica version of SymmetricGroup, if indeed it's any different from the new one. $\endgroup$ – Simon Oct 7 at 11:37

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