1

I'm trying to implement the nth permutation (nPr => per(n,L,Out)) but I keep getting a false.

Here's what I'm trying to do;

per(0,_,[]).
per(_,[],[]).
per(R,[H|T1],[H|T]):-
    R1 is R-1,
    per(R1,T1,[H|T]),
    per(R1,T1,T).

What am I doing wrong?

Also is there (an easier) way to implement nth permutation (nPr) using the built in permutation predicate?

false
  • 10,264
  • 13
  • 101
  • 209
steoiatsl
  • 1,892
  • 2
  • 22
  • 39
  • 1
    The n-th permutation, according to the lexicographical order, can be computed [as described in the this article on Permutations](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order). Although it probably makes for a more tedious Prolog exercise. – lurker Mar 28 '16 at 16:24

2 Answers2

1

The naive solution would be to collect all permutation using findall/3 or bagof/3 and then pick the one you need from the list.

If you are using SWI-Prolog, you could use offset/2 from library(solution_sequences).

once( offset(N, permutation(List, Permutation)) )

Or, you could also take a look at this answer for a definition of call_nth/2, and with it:

call_nth(permutation(List, Permutation), N)

But of course, if you are serious about this, you should rather find the n-th permutation of the indices of your list, and use this to generate the permutation.

Community
  • 1
  • 1
0
per(R1,T1,[H|T]),
per(R1,T1,T).

What you're stating here, is that the R1-th permutation of T1 is both equal to [H|T] and T. That can't possibly be what you mean.

Also, per your per(0,_,[])., the zeroth permutation of anything is an empty list. But wouldn't be the zeroth permutation of a list, be the list itself? In other words, per(0, L, L)?
(Or do I misunderstand the numbering of permutations?)

SQB
  • 3,926
  • 2
  • 28
  • 49