6
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\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
    Commented Oct 6, 2019 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
    Commented Oct 6, 2019 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
    Commented Oct 6, 2019 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
    Commented Oct 6, 2019 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
    Commented Oct 6, 2019 at 15:38

5 Answers 5

Reset to default
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}

Improve this answer
$\endgroup$
3
  • $\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
    Commented Oct 7, 2019 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
    Commented Oct 7, 2019 at 7:39
  • 3
    $\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
    Commented Oct 7, 2019 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

Improve this answer
$\endgroup$
4
  • $\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
    Commented Oct 7, 2019 at 7:41
  • $\begingroup$ Note that FindFile["Combinatorica`"] gives a hint where to look for the file. $\endgroup$
    – Michael E2
    Commented Oct 7, 2019 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
    Commented Oct 8, 2019 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
    Commented Oct 8, 2019 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}}
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you ... this is indeed quite useful ... very significant speed up ... $\endgroup$
    – EGME
    Commented Oct 7, 2019 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]
Improve this answer
$\endgroup$
1
  • $\begingroup$ The source code of Combinatorica is available. It's better to read the source file, in case there are any comments. $\endgroup$
    – Szabolcs
    Commented Oct 7, 2019 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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I'd be curious to know what it is that you need from Combinatorica that you cannot get elsewhere. $\endgroup$
    – Szabolcs
    Commented Oct 7, 2019 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
    Commented Oct 7, 2019 at 11:37
  • $\begingroup$ @Szabolcs I found a nasty graph related bug which calls for a replacement. However, I do not wish to post about bugs here, so I could send you a very short notebook with the example if you can be reached? By the way, why was this question closed ... I did not see parallel prior questions with these good answers, although it really doesn’t matter ... it has served its purpose, but that is not the reason given for its closure ... Apologies for asking, and thank you at the same time, I thought you might know, and also, be interested in the first issue ... $\endgroup$
    – EGME
    Commented Nov 29, 2019 at 16:43

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