Prolog Permutations

[Joseph Haley]

I'm trying to get more into learning prolog as I'll be taking an AI class at school next semester. I've been able to get down the basics down and can do relation based stuff, however, I've been trying to learn permutations and combinatronics and they seem pretty straightforward, but it led me to a question that I can't figure out how to solve. Say I wanted to know the permutations of 1's and 0's with a certain condition that there must be a minimum of 4 1's before they're placed so 111000000 wouldn't be valid as 3<4 but 111110000 would be.

I have no idea where I would start to try and find a solution for this so any help is greatly appreciated, but in the end I want the code to do something like this:

?- placeOnesAndZeros(9,X). %where 9 is the length of the list/array and X is the permutations

    [1,1,1,1,0,0,0,0,0]

    [0,1,1,1,1,0,0,0,0]

    [0,0,1,1,1,1,0,0,0]

    [0,0,0,1,1,1,1,0,0]

    [0,0,0,0,1,1,1,1,0]

    [0,0,0,0,0,1,1,1,1]

    [1,1,1,1,0,1,1,1,1]

    [1,1,1,1,1,0,0,0,0]

    [0,1,1,1,1,1,0,0,0]

    [0,0,1,1,1,1,1,0,0]

    [0,0,0,1,1,1,1,1,0]

    [0,0,0,0,1,1,1,1,1]

    [1,1,1,1,1,1,0,0,0]

    [0,1,1,1,1,1,1,0,0]

    [0,0,1,1,1,1,1,1,0]

    [0,0,0,1,1,1,1,1,1]

    [1,1,1,1,1,1,1,0,0]

    [0,1,1,1,1,1,1,1,0]

    [0,0,1,1,1,1,1,1,1]

    [1,1,1,1,1,1,1,1,0]

    [0,1,1,1,1,1,1,1,1]

    [1,1,1,1,1,1,1,1,1]

Thank you in advance!

[Markus Triska]

Hi Joseph,

for reasoning about the number of occurrences of fixed integers in a list, consider using the library predicate global_cardinality/2. It lets you express such conditions very conveniently and works in many directions.

For example, your concrete use case can be expressed with:

?- length(Ls, 9),

   global_cardinality(Ls, [0-_,1-Ones]),

   Ones #>= 4,

   label(Ls).

Ls = [0, 0, 0, 0, 0, 1, 1, 1, 1],

Ones = 4 ;

Ls = [0, 0, 0, 0, 1, 0, 1, 1, 1],

Ones = 4 ;

Ls = [0, 0, 0, 0, 1, 1, 0, 1, 1],

Ones = 4 ;

Ls = [0, 0, 0, 0, 1, 1, 1, 0, 1],

Ones = 4 .

Note also the use of library predicates (#>=)/2 and label/1 for restricting the range of integers and enumeration of integer variables, respectively.

All the best!

Markus

[Barb Knox]

On 25/11/2017, at 14:06, Joseph Haley <josephhal...@gmail.com> wrote:

I'm trying to get more into learning prolog as I'll be taking an AI class at school next semester. I've been able to get down the basics down and can do relation based stuff, however, I've been trying to learn permutations and combinatorics and they seem pretty straightforward, but it led me to a question that I can't figure out how to solve. Say I wanted to know the permutations of 1’s and 0's with a certain condition that there must be at least 4 1's in a row.

I infer from your example answer below that this means there must be at least 4 contiguous 1’s in each listed row, right?  (“In a row” is somewhat ambiguous.)

As a mathematical combinatorics problem, it’s tricky to handle any other 1’s that happen to be adjacent to the required 1111, and any other 1111 in addition to the required 1111.

You can brute-force this in Prolog by generating each of the 2^9 possible nine-digit binary sequences and scanning each one looking for 1111.  Inelegant, but effective.

Also, in general combinatorics has only a small role in AI.  I am sure that there are books and Internet resources which deal directly with introductory Prolog for AI.  Google is your friend (except for its Evil aspects; I use startpage.com).

— Barb

I have no idea where I would start to try and find a solution for this, but in the end I want the code to do something like this:

?- placeOnesAndZeros(9,X). %where 9 is the length of the list/array and X is the permutations

    [0,0,0,0,0,0,0,0,0]

[Joseph Haley]

Thank you very much, between here and StackExchange I was able to figure it out. I made a seperate functor that searches through the list and replaces 1's with 0's if there aren't enough 1's and then it strips the 0's from the list and outputs the *final* list.