How to create every possible 4 digit code, out of 6 numbers and without using duplicates?

user_8583502 0
Viewed 235

I'm trying to create a list that contains every possible 4-digit code, using numbers from 1 to 6. I can't use duplicates, so [1, 2, 3, 3] is not allowed.

I came up with the idea to first create all 1296 possible codes WITH using duplicates and then filtering out every code that doesn't fit the rule: no duplicates. In order to do this I would need to first create these 1296 codes. So starting with [1, 1, 1, 1] and ending with [6, 6, 6, 6].

Can somebody help me out? I know it should do [1, 1, 1, 1] and then [1, 1, 1, 2] etcetera, but I don't know how to implement this.

I forgot to mention: I started of by trying to create one single code that followed the rules. This didn't go so well either. This was my code:

single_code([]).
single_code(Code1):-
  length(Code1, Y),
  Y < 4,
  random_between(1, 6, X),
  \+member(X, Code1),
  single_code([X|Code1]).
single_code(Code1):-
  single_code(Code1).

It eventually went into a loop and I don't know how to stop it from doing that. There is something I don't understand about recursion and I don't know what.

prolog
1 Answers

Using predicates and builtins

A possible idea is to user member/2. Although member/2 can perform member-checks, it does more: it can enumerate over alle elements of a list (e.g. member(X,[1,4,2,5])), or construct all possible lists where a certain value is a member (e.g. member(2,L)).

Here we can use it to enumerate over the possibilities. So member(A,[1,2,3,4,5,6]). will unify X with 1, 2, ..., 6.

We can use this to exhaustively enumerate all possible lists with four elements like:

four([A,B,C,D]) :-
    member(A,[1,2,3,4,5,6]),
    member(B,[1,2,3,4,5,6]),
    member(C,[1,2,3,4,5,6]),
    member(D,[1,2,3,4,5,6]).

which will by backtracing produce all lists with four elements. Such that the eBlements are all members of the lists [1,2,3,4,5,6].

Now of course we will also produce things like [2,2,3,3] where there are duplicates. We can however easily add A \= B as a constraint to check whether A is not equal to B. So by adding six constraints, we can prevent any duplicate elements:

four([A,B,C,D]) :-
    member(A,[1,2,3,4,5,6]),
    member(B,[1,2,3,4,5,6]),
    member(C,[1,2,3,4,5,6]),
    member(D,[1,2,3,4,5,6]),
    A \= B,
    A \= C,
    A \= D,
    B \= C,
    B \= D,
    C \= D.

Now this is however still inefficient: we here perform a generate-and-test approach where we first generate a full sample, and then check if it is valid. But if for instance A and B are equal, then regardless of the values we pick for C and D, we can already backtrack. So usually it is better to interleave generating and testing, like:

four([A,B,C,D]) :-
    member(A,[1,2,3,4,5,6]),
    member(B,[1,2,3,4,5,6]),
    A \= B,
    member(C,[1,2,3,4,5,6]),
    A \= C,
    B \= C,
    member(D,[1,2,3,4,5,6]),
    A \= D,
    B \= D,
    C \= D.

Now it works more efficient, but it is still inelegant: a lot of code is repeated. It makes it very hard to for instance generate lists with six elements without any duplicates. We can solve this by generalizing the approach.

The first thing we need is a way to generate members of a virtual list [1..n]. We can do this with:

between(A,B,A) :-
    A =< B.
between(A,B,C) :-
    A < B,
    A1 is A+1,
    between(A1,B,C).

If we call between(1,6,X). it will unify X with all the elements 1, 2, 3, 4, 5, and 6.

So now we can declare a more generic variant:

distinct_n(A,B,N,L) :-
    distinct_n(A,B,N,[],L).

distinct_n(_,_,0,_,[]).
distinct_n(A,B,N,Xs,[X|R]) :-
    N > 0,
    between(A,B,X),
    \+ member(X,Xs),
    N1 is N-1,
    distinct_n(A,B,N1,[X|Xs],R).

So now we can generate a list L with N numbers from A to B (both inclusive), with distinct_n(A,B,N,L)..

If we now thus generate all 3-lists with distinct elements ranging from 1-4, we obtain:

?- distinct_n(1,4,3,L).
L = [1, 2, 3] ;
L = [1, 2, 4] ;
L = [1, 3, 2] ;
L = [1, 3, 4] ;
L = [1, 4, 2] ;
L = [1, 4, 3] ;
L = [2, 1, 3] ;
L = [2, 1, 4] ;
L = [2, 3, 1] ;
L = [2, 3, 4] ;
L = [2, 4, 1] ;
L = [2, 4, 3] ;
L = [3, 1, 2] ;
L = [3, 1, 4] ;
L = [3, 2, 1] ;
L = [3, 2, 4] ;
L = [3, 4, 1] ;
L = [3, 4, 2] ;
L = [4, 1, 2] ;
L = [4, 1, 3] ;
L = [4, 2, 1] ;
L = [4, 2, 3] ;
L = [4, 3, 1] ;
L = [4, 3, 2] ;
false.

If we now want to generate a list of these lists, we can use findall/3:

?- findall(L,distinct_n(1,4,3,L),LL).
LL = [[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2, 1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3], [3, 1, 2], [3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1, 3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]].

Using CLP(FD)

Prolog also has a Constraint Logic Programming library over Finite Domains (clpfd). This allows to specify code in a short way, like:

:- use_module(library(clpfd)).

distinct_n(A,B,N,L) :-
    length(L,N),
    L ins A..B,
    all_distinct(L),
    label(L).

Se we first import the library, then we construct a list L of length N. All the elements of L are in A..B, and the elements are all_distinct/1. Finally by using label/1 we start a procedure to find solutions to the constraint logic programming problem.

user_675790
Related