Inverse Factorial Function (Prolog)

1
votes

I have to write a Prolog program to computer the inverse of factorial function without using division. I was also given the note: "the inverse of a function is not necessarily a function". I have this as a normal factorial predicate..

fact(0,1).
fact(N,F) :- N>0, N1 is N-1, fact(N1,F1), F is N * F1.

I've read on some other posts that you should be able to just switch around the arguments, but that doesn't seem to be the case with this version. Could anyone help me out with figuring out why?

3
prologfactorial
because N>0 demands N be a ground arithmetic value. and so does N1 is N-1 bit. - Will Ness
what that remark means is that the call invfact(X,1) should succeed twice. Right? - Will Ness
I believe so. So I would have to change the body of the function? - user2796815
I would use your fact changed into a generative predicate - such that generates a list of factorials up to a given value - as pairs is better, (N, F) where F is N! - and then search that list back from end for my index. - Will Ness
I'm pretty unfamiliar with Prolog. Is it possible to point me in the right direction on how to complete this? - user2796815

3 Answers

2
votes

See Inverse factorial in Prolog for a clean, relational solution, but if we are at it:

inv_fact(RF, N) :-
   (  between(0,RF,N),
      fact(N,F),
      F >= RF
   -> F = RF
   ;  false
   ).
inv_fact(1, 1).
1
votes

How about this? We simply generate factorials as we go using your predicate fact/2, and if we get to a point where we have a matching factorial we stop, otherwise we generate next one.

fact(0,1).
fact(N,F) :- N>0, N1 is N-1, fact(N1,F1), F is N * F1.

inv_fact(1,0).
inv_fact(Value,Number) :- inv_fact(Value,1,Number).


inv_fact(Value,Num,Num) :- fact(Num,Value).
inv_fact(Value,Num,Number) :- fact(Num,V), Value < V,!,false.
inv_fact(Value,Num,Number) :- fact(Num,V),
                              not(Value=V),
                              NumNew is Num+1,
                              inv_fact(Value,NumNew,Number).
0
votes

I think you need to change the logic, reversing the evaluation 'flow'. N is the unknown, but fact/2 assumes is bound.

If you make fact/2 tail recursive, adding an accumulator, you will be in better position to solve this problem, since you could also add the the known factorial (say K) and the unknown (say U), and then test:

 if F1 equals K (we have found the solution), unify U to N
 if F1 > K, there is no solution... let Prolog fail...

Otherwise, kind of cheating...

?- between(1,inf,X), fact(X,F), F >= 120.
X = 5,
F = 120

edit of course, that snippet is not only a cheat, it's awfully inefficient.

An efficient one, implementing the hint I give above

factinv(1, 0). % conventional
factinv(K, U) :- factinv(1, K, 1, U).
factinv(C, K, N, U) :-
    F is C * N,
    (   F < K
    ->  M is N+1,
        factinv(F, K, M, U)
    ;   F == K
    ->  N = U
    ).