Inverse Factorial Function (Prolog)

Question

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?

because `N>0` demands `N` be a ground arithmetic value. and so does `N1 is N-1` bit. — Will Ness, Nov 12 '13 at 22:29
what that remark means is that the call `invfact(X,1)` should succeed *twice*. Right? — Will Ness, Nov 12 '13 at 22:32
I believe so. So I would have to change the body of the function? — user2796815, Nov 12 '13 at 22:47
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, Nov 12 '13 at 22:50
I'm pretty unfamiliar with Prolog. Is it possible to point me in the right direction on how to complete this? — user2796815, Nov 12 '13 at 23:11
possible duplicate of [Inverse factorial in prolog](http://stackoverflow.com/questions/19025664/inverse-factorial-in-prolog) — false, Nov 12 '13 at 23:17

score 2 · Answer 1 · edited May 23 '17 at 12:23

2

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).

edited May 23 '17 at 12:23

Community

1
1

answered Nov 12 '13 at 23:59

false

10,264
13
101
209

ssbarbee · Answer 2 · 2013-11-12T23:59:23.507

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).

Thanks false for helping me improve my answer. – ssbarbee Nov 12 '13 at 23:59 — ssbarbee, Nov 12 '13 at 23:59

CapelliC · Answer 3 · 2013-11-13T07:37:20.153

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
    ).

Inverse Factorial Function (Prolog)

3 Answers3