Prolog Permutations with Condition for Multiple Elements

up vote
0
down vote

favorite

I have a program to generate all the permutations of a list where for each 2<=i<=n, there is a 1<=j<i where |v(i)-v(j)|=1

For example, for [1,2,3], the results are:

[1,2,3]

[2,1,3]

[2,3,1]

[3,2,1]

[1,3,2] and [3,1,2] would be wrong because |3-1| and |1-3| are not 1

The code is:

takeout([X|T],X,T).

takeout([H|L],X,[H|T]) :-

    takeout(L,X,T).



takeout1([X|T],P,X,T) :-

    D is abs(X-P),

    D =:= 1.

takeout1([H|L],N,X,[H|T]) :-

    takeout1(L,N,X,T).



perm1(,).

perm1(L,[E|T]) :-

    takeout(L,E,R),

    perm_abs(R,E,T).



perm_abs(,_,).

perm_abs(L,O,[E|T]) :-

    takeout1(L,O,E,R),

    perm_abs(R,E,T).



perm(N,R):-

    numlist(1,N,L),

    perm1(L,R).

This code gives only the consecutive results. I think I am supposed to change something at takeout1, but I do not know where exactly.

Thank you in advance.

edited Nov 13 at 0:22

false

10.9k769141

asked Nov 11 at 19:19

Barrett

1

What are i and j here? It is not perfectly clear to me what your constraint is.
– Willem Van Onsem
Nov 11 at 19:21

1

Furthermore given your original list contains only [1,2,...,k], indeed the only permutations that are valid are [1,2,...,k] and [k,k-1,...1], since every other "swap" will result in a "gap" somewhere else.
– Willem Van Onsem
Nov 11 at 19:22

1

for each 2<=i<=n, there is a 1<=j... What do these variables i, n, and j represent in this condition?
– lurker
Nov 11 at 19:27

"i" are the numbers from the second position of the list to the last one, and "j" are the numbers before "i"
– Barrett
Nov 11 at 20:01

add a comment |

up vote
0
down vote

favorite

I have a program to generate all the permutations of a list where for each 2<=i<=n, there is a 1<=j<i where |v(i)-v(j)|=1

For example, for [1,2,3], the results are:

[1,2,3]

[2,1,3]

[2,3,1]

[3,2,1]

[1,3,2] and [3,1,2] would be wrong because |3-1| and |1-3| are not 1

The code is:

takeout([X|T],X,T).

takeout([H|L],X,[H|T]) :-

    takeout(L,X,T).



takeout1([X|T],P,X,T) :-

    D is abs(X-P),

    D =:= 1.

takeout1([H|L],N,X,[H|T]) :-

    takeout1(L,N,X,T).



perm1(,).

perm1(L,[E|T]) :-

    takeout(L,E,R),

    perm_abs(R,E,T).



perm_abs(,_,).

perm_abs(L,O,[E|T]) :-

    takeout1(L,O,E,R),

    perm_abs(R,E,T).



perm(N,R):-

    numlist(1,N,L),

    perm1(L,R).

This code gives only the consecutive results. I think I am supposed to change something at takeout1, but I do not know where exactly.

Thank you in advance.

edited Nov 13 at 0:22

false

10.9k769141

asked Nov 11 at 19:19

Barrett

1

What are i and j here? It is not perfectly clear to me what your constraint is.
– Willem Van Onsem
Nov 11 at 19:21

1

Furthermore given your original list contains only [1,2,...,k], indeed the only permutations that are valid are [1,2,...,k] and [k,k-1,...1], since every other "swap" will result in a "gap" somewhere else.
– Willem Van Onsem
Nov 11 at 19:22

1

for each 2<=i<=n, there is a 1<=j... What do these variables i, n, and j represent in this condition?
– lurker
Nov 11 at 19:27

"i" are the numbers from the second position of the list to the last one, and "j" are the numbers before "i"
– Barrett
Nov 11 at 20:01

add a comment |

up vote
0
down vote

favorite

I have a program to generate all the permutations of a list where for each 2<=i<=n, there is a 1<=j<i where |v(i)-v(j)|=1

For example, for [1,2,3], the results are:

[1,2,3]

[2,1,3]

[2,3,1]

[3,2,1]

[1,3,2] and [3,1,2] would be wrong because |3-1| and |1-3| are not 1

The code is:

takeout([X|T],X,T).

takeout([H|L],X,[H|T]) :-

    takeout(L,X,T).



takeout1([X|T],P,X,T) :-

    D is abs(X-P),

    D =:= 1.

takeout1([H|L],N,X,[H|T]) :-

    takeout1(L,N,X,T).



perm1(,).

perm1(L,[E|T]) :-

    takeout(L,E,R),

    perm_abs(R,E,T).



perm_abs(,_,).

perm_abs(L,O,[E|T]) :-

    takeout1(L,O,E,R),

    perm_abs(R,E,T).



perm(N,R):-

    numlist(1,N,L),

    perm1(L,R).

This code gives only the consecutive results. I think I am supposed to change something at takeout1, but I do not know where exactly.

Thank you in advance.

edited Nov 13 at 0:22

false

10.9k769141

asked Nov 11 at 19:19

Barrett

I have a program to generate all the permutations of a list where for each 2<=i<=n, there is a 1<=j<i where |v(i)-v(j)|=1

For example, for [1,2,3], the results are:

[1,2,3]

[2,1,3]

[2,3,1]

[3,2,1]

[1,3,2] and [3,1,2] would be wrong because |3-1| and |1-3| are not 1

The code is:

takeout([X|T],X,T).

takeout([H|L],X,[H|T]) :-

    takeout(L,X,T).



takeout1([X|T],P,X,T) :-

    D is abs(X-P),

    D =:= 1.

takeout1([H|L],N,X,[H|T]) :-

    takeout1(L,N,X,T).



perm1(,).

perm1(L,[E|T]) :-

    takeout(L,E,R),

    perm_abs(R,E,T).



perm_abs(,_,).

perm_abs(L,O,[E|T]) :-

    takeout1(L,O,E,R),

    perm_abs(R,E,T).



perm(N,R):-

    numlist(1,N,L),

    perm1(L,R).

This code gives only the consecutive results. I think I am supposed to change something at takeout1, but I do not know where exactly.

Thank you in advance.

prolog permutation

edited Nov 13 at 0:22

false

10.9k769141

asked Nov 11 at 19:19

Barrett

edited Nov 13 at 0:22

false

10.9k769141

asked Nov 11 at 19:19

Barrett

edited Nov 13 at 0:22

false

10.9k769141

edited Nov 13 at 0:22

false

10.9k769141

edited Nov 13 at 0:22

false

10.9k769141

asked Nov 11 at 19:19

Barrett

asked Nov 11 at 19:19

Barrett

asked Nov 11 at 19:19

Barrett

1

What are i and j here? It is not perfectly clear to me what your constraint is.
– Willem Van Onsem
Nov 11 at 19:21

1

Furthermore given your original list contains only [1,2,...,k], indeed the only permutations that are valid are [1,2,...,k] and [k,k-1,...1], since every other "swap" will result in a "gap" somewhere else.
– Willem Van Onsem
Nov 11 at 19:22

1

for each 2<=i<=n, there is a 1<=j... What do these variables i, n, and j represent in this condition?
– lurker
Nov 11 at 19:27

"i" are the numbers from the second position of the list to the last one, and "j" are the numbers before "i"
– Barrett
Nov 11 at 20:01

add a comment |

1

What are i and j here? It is not perfectly clear to me what your constraint is.
– Willem Van Onsem
Nov 11 at 19:21

1

Furthermore given your original list contains only [1,2,...,k], indeed the only permutations that are valid are [1,2,...,k] and [k,k-1,...1], since every other "swap" will result in a "gap" somewhere else.
– Willem Van Onsem
Nov 11 at 19:22

1

for each 2<=i<=n, there is a 1<=j... What do these variables i, n, and j represent in this condition?
– lurker
Nov 11 at 19:27

"i" are the numbers from the second position of the list to the last one, and "j" are the numbers before "i"
– Barrett
Nov 11 at 20:01

What are i and j here? It is not perfectly clear to me what your constraint is.
– Willem Van Onsem
Nov 11 at 19:21

Furthermore given your original list contains only [1,2,...,k], indeed the only permutations that are valid are [1,2,...,k] and [k,k-1,...1], since every other "swap" will result in a "gap" somewhere else.
– Willem Van Onsem
Nov 11 at 19:22

for each 2<=i<=n, there is a 1<=j... What do these variables i, n, and j represent in this condition?
– lurker
Nov 11 at 19:27

"i" are the numbers from the second position of the list to the last one, and "j" are the numbers before "i"
– Barrett
Nov 11 at 20:01

add a comment |

1 Answer
1

active

oldest

votes

up vote
1
down vote

accepted

valid(R) :-

    forall((nth1(I,R,X), I>1), (nth1(J,R,Y), J<I, 1 =:= abs(X-Y))).



?- forall((N=4, numlist(1,N,L), permutation(L,R), valid(R)),writeln(R)).

[1,2,3,4]

[2,1,3,4]

[2,3,1,4]

[2,3,4,1]

[3,2,1,4]

[3,2,4,1]

[3,4,2,1]

[4,3,2,1]

true.

You can add valid/1 after the intermediate permutation step, to get early filtering of invalid configurations.

edited Nov 12 at 11:56

answered Nov 12 at 8:53

CapelliC

50.8k43262

It works for N = 3, but for N = 4, it writes the result twice and it also writes [1,4,3,2], which is wrong, because |4-1|=3, not 1. For N=5 it writes the result three times and also gives some wrong answers
– Barrett
Nov 12 at 11:10

Sorry, my bad... now should work. Check it out. Anyway, the idea is to separate the validity check from the generation.
– CapelliC
Nov 12 at 11:56

Thank you very much! It works for all cases!
– Barrett
Nov 12 at 14:22

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53252305%2fprolog-permutations-with-condition-for-multiple-elements%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

up vote
1
down vote

accepted

valid(R) :-

    forall((nth1(I,R,X), I>1), (nth1(J,R,Y), J<I, 1 =:= abs(X-Y))).



?- forall((N=4, numlist(1,N,L), permutation(L,R), valid(R)),writeln(R)).

[1,2,3,4]

[2,1,3,4]

[2,3,1,4]

[2,3,4,1]

[3,2,1,4]

[3,2,4,1]

[3,4,2,1]

[4,3,2,1]

true.

You can add valid/1 after the intermediate permutation step, to get early filtering of invalid configurations.

edited Nov 12 at 11:56

answered Nov 12 at 8:53

CapelliC

50.8k43262

It works for N = 3, but for N = 4, it writes the result twice and it also writes [1,4,3,2], which is wrong, because |4-1|=3, not 1. For N=5 it writes the result three times and also gives some wrong answers
– Barrett
Nov 12 at 11:10

Sorry, my bad... now should work. Check it out. Anyway, the idea is to separate the validity check from the generation.
– CapelliC
Nov 12 at 11:56

Thank you very much! It works for all cases!
– Barrett
Nov 12 at 14:22

add a comment |

up vote
1
down vote

accepted

valid(R) :-

    forall((nth1(I,R,X), I>1), (nth1(J,R,Y), J<I, 1 =:= abs(X-Y))).



?- forall((N=4, numlist(1,N,L), permutation(L,R), valid(R)),writeln(R)).

[1,2,3,4]

[2,1,3,4]

[2,3,1,4]

[2,3,4,1]

[3,2,1,4]

[3,2,4,1]

[3,4,2,1]

[4,3,2,1]

true.

You can add valid/1 after the intermediate permutation step, to get early filtering of invalid configurations.

edited Nov 12 at 11:56

answered Nov 12 at 8:53

CapelliC

50.8k43262

It works for N = 3, but for N = 4, it writes the result twice and it also writes [1,4,3,2], which is wrong, because |4-1|=3, not 1. For N=5 it writes the result three times and also gives some wrong answers
– Barrett
Nov 12 at 11:10

Sorry, my bad... now should work. Check it out. Anyway, the idea is to separate the validity check from the generation.
– CapelliC
Nov 12 at 11:56

Thank you very much! It works for all cases!
– Barrett
Nov 12 at 14:22

add a comment |

up vote
1
down vote

accepted

valid(R) :-

    forall((nth1(I,R,X), I>1), (nth1(J,R,Y), J<I, 1 =:= abs(X-Y))).



?- forall((N=4, numlist(1,N,L), permutation(L,R), valid(R)),writeln(R)).

[1,2,3,4]

[2,1,3,4]

[2,3,1,4]

[2,3,4,1]

[3,2,1,4]

[3,2,4,1]

[3,4,2,1]

[4,3,2,1]

true.

You can add valid/1 after the intermediate permutation step, to get early filtering of invalid configurations.

edited Nov 12 at 11:56

answered Nov 12 at 8:53

CapelliC

50.8k43262

valid(R) :-

    forall((nth1(I,R,X), I>1), (nth1(J,R,Y), J<I, 1 =:= abs(X-Y))).



?- forall((N=4, numlist(1,N,L), permutation(L,R), valid(R)),writeln(R)).

[1,2,3,4]

[2,1,3,4]

[2,3,1,4]

[2,3,4,1]

[3,2,1,4]

[3,2,4,1]

[3,4,2,1]

[4,3,2,1]

true.

You can add valid/1 after the intermediate permutation step, to get early filtering of invalid configurations.

edited Nov 12 at 11:56

answered Nov 12 at 8:53

CapelliC

50.8k43262

edited Nov 12 at 11:56

answered Nov 12 at 8:53

CapelliC

50.8k43262

answered Nov 12 at 8:53

CapelliC

50.8k43262

answered Nov 12 at 8:53

CapelliC

50.8k43262

It works for N = 3, but for N = 4, it writes the result twice and it also writes [1,4,3,2], which is wrong, because |4-1|=3, not 1. For N=5 it writes the result three times and also gives some wrong answers
– Barrett
Nov 12 at 11:10

Sorry, my bad... now should work. Check it out. Anyway, the idea is to separate the validity check from the generation.
– CapelliC
Nov 12 at 11:56

Thank you very much! It works for all cases!
– Barrett
Nov 12 at 14:22

add a comment |

It works for N = 3, but for N = 4, it writes the result twice and it also writes [1,4,3,2], which is wrong, because |4-1|=3, not 1. For N=5 it writes the result three times and also gives some wrong answers
– Barrett
Nov 12 at 11:10

Sorry, my bad... now should work. Check it out. Anyway, the idea is to separate the validity check from the generation.
– CapelliC
Nov 12 at 11:56

Thank you very much! It works for all cases!
– Barrett
Nov 12 at 14:22

It works for N = 3, but for N = 4, it writes the result twice and it also writes [1,4,3,2], which is wrong, because |4-1|=3, not 1. For N=5 it writes the result three times and also gives some wrong answers
– Barrett
Nov 12 at 11:10

Sorry, my bad... now should work. Check it out. Anyway, the idea is to separate the validity check from the generation.
– CapelliC
Nov 12 at 11:56

Thank you very much! It works for all cases!
– Barrett
Nov 12 at 14:22

add a comment |

draft saved

draft discarded

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Cfrgtkky