7
\$\begingroup\$

Given an array of integers as input(including negative integers), find all (can include duplicates) permutations that do not have the same number next to each other, then print them all out.
If no permutations were found, print Nothing or return an empty list or any consistent output indicating that none were found.
Note that the original array can be a permutation.

Test cases:

[0, 1, 1, 0] -> [1, 0, 1, 0], [0, 1, 0, 1]
[0, 1, 2, 0] -> [0, 1, 2, 0], [0, 2, 1, 0], [1, 0, 2, 0], [0, 1, 0, 2], [2, 0, 1, 0], [0, 2, 0, 1]
[0, 1, 0] -> [0, 1, 0]
[1, 1, 1] -> [] or Nothing
[0, 0, 1, 1] -> [0, 1, 0, 1], [1, 0, 1, 0]

This is , all usual golfing rules apply and the shortest answer (in bytes) wins!

Leaderboard:

var QUESTION_ID=244078;
var OVERRIDE_USER=8478;
var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;function answersUrl(d){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(d,e){return"https://api.stackexchange.com/2.2/answers/"+e.join(";")+"/comments?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){answers.push.apply(answers,d.items),answers_hash=[],answer_ids=[],d.items.forEach(function(e){e.comments=[];var f=+e.share_link.match(/\d+/);answer_ids.push(f),answers_hash[f]=e}),d.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){d.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),d.has_more?getComments():more_answers?getAnswers():process()}})}getAnswers();var SCORE_REG=function(){var d=String.raw`h\d`,e=String.raw`\-?\d+\.?\d*`,f=String.raw`[^\n<>]*`,g=String.raw`<s>${f}</s>|<strike>${f}</strike>|<del>${f}</del>`,h=String.raw`[^\n\d<>]*`,j=String.raw`<[^\n<>]+>`;return new RegExp(String.raw`<${d}>`+String.raw`\s*([^\n,]*[^\s,]),.*?`+String.raw`(${e})`+String.raw`(?=`+String.raw`${h}`+String.raw`(?:(?:${g}|${j})${h})*`+String.raw`</${d}>`+String.raw`)`)}(),OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(d){return d.owner.display_name}function process(){var d=[];answers.forEach(function(n){var o=n.body;n.comments.forEach(function(q){OVERRIDE_REG.test(q.body)&&(o="<h1>"+q.body.replace(OVERRIDE_REG,"")+"</h1>")});var p=o.match(SCORE_REG);p&&d.push({user:getAuthorName(n),size:+p[2],language:p[1],link:n.share_link})}),d.sort(function(n,o){var p=n.size,q=o.size;return p-q});var e={},f=1,g=null,h=1;d.forEach(function(n){n.size!=g&&(h=f),g=n.size,++f;var o=jQuery("#answer-template").html();o=o.replace("{{PLACE}}",h+".").replace("{{NAME}}",n.user).replace("{{LANGUAGE}}",n.language).replace("{{SIZE}}",n.size).replace("{{LINK}}",n.link),o=jQuery(o),jQuery("#answers").append(o);var p=n.language;p=jQuery("<i>"+n.language+"</i>").text().toLowerCase(),e[p]=e[p]||{lang:n.language,user:n.user,size:n.size,link:n.link,uniq:p}});var j=[];for(var k in e)e.hasOwnProperty(k)&&j.push(e[k]);j.sort(function(n,o){return n.uniq>o.uniq?1:n.uniq<o.uniq?-1:0});for(var l=0;l<j.length;++l){var m=jQuery("#language-template").html(),k=j[l];m=m.replace("{{LANGUAGE}}",k.lang).replace("{{NAME}}",k.user).replace("{{SIZE}}",k.size).replace("{{LINK}}",k.link),m=jQuery(m),jQuery("#languages").append(m)}}
body{text-align:left!important}#answer-list{padding:10px;float:left}#language-list{padding:10px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/primary.css?v=f52df912b654"> <div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table>

\$\endgroup\$
8
  • 9
    \$\begingroup\$ Welcome to Code Golf, and nice first question! I'd suggest you remove the Nothing output requirement, because it doesn't really make the task more interesting; I think returning an empty list (instead of a lists of lists) is more sensible. \$\endgroup\$
    – pxeger
    Mar 13, 2022 at 17:30
  • 8
    \$\begingroup\$ Could you specify whether or not the result may contain duplicates? \$\endgroup\$ Mar 13, 2022 at 17:56
  • 1
    \$\begingroup\$ Are the numbers non-negative integers? Number on it's own is pretty ambiguous but the test cases all contain only positive integers. \$\endgroup\$
    – Wheat Wizard
    Mar 13, 2022 at 18:11
  • 1
    \$\begingroup\$ Yes! You can have tuples! \$\endgroup\$
    – Joao-3
    Mar 13, 2022 at 19:28
  • 3
    \$\begingroup\$ @pxeger I made that rule optional. \$\endgroup\$
    – Joao-3
    Mar 13, 2022 at 19:38

13 Answers 13

3
\$\begingroup\$

Vyxal, 4 bytes

Ṗ'¯A

Try it Online!

Port of Jonathan Allan's Jelly answer.

-1 thanks to ovs.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think ṖU'¯A should work for 5 \$\endgroup\$
    – ovs
    Mar 14, 2022 at 7:19
  • \$\begingroup\$ @ovs Oh yeah, thanks :) \$\endgroup\$
    – emanresu A
    Mar 14, 2022 at 7:42
  • \$\begingroup\$ You can now remove U \$\endgroup\$ Mar 26, 2022 at 16:14
3
\$\begingroup\$

J, 30 bytes

[:~.@(#~0=1#.2=/\"1])i.@!@#A.]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Factor + grouping.extras math.combinatorics, 59 bytes

[ [ [ = ] 2clump-map vnone? ] filter-permutations members ]

Try it online!

  • [ ... ] filter-permutations Select the permutations of the input for which [ ... ] returns true.
  • [ = ] 2clump-map Map = to every two elements of a sequence with overlapping. e.g. { 1 0 1 1 2 } [ = ] 2clump-map -> { f f t f }
  • vnone? Returns true only if every element of a sequence is f.
  • members Get the unique elements of a sequence.
\$\endgroup\$
3
\$\begingroup\$

BQN, 35 bytesSBCS

{(∧´1«»≠⊢)¨⊸/⍷𝕩⊏˜⚇1⍋∘⍋⊸≡˜¨⊸/⥊↕⥊˜≠𝕩}

Run online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Rules now say "Nothing" part is optional. \$\endgroup\$
    – Jonah
    Mar 13, 2022 at 20:10
  • \$\begingroup\$ @Jonah thanks for telling me, updated \$\endgroup\$
    – ovs
    Mar 13, 2022 at 20:48
3
+50
\$\begingroup\$

PARI/GP, 73 bytes

f(x)=r=[];forperm(vecsort(x),p,prod(i=2,#p,p[i]-p[i-1])&&r=concat(r,p));r

Attempt This Online!

After a lot of head scratching and asking @alephalpha in chat, here it is.

\$\endgroup\$
3
\$\begingroup\$

C++ (gcc), 310 301 283 278 bytes

EDIT: -22 bytes thanks to ceilingcat and -1 byte from the label statement.

#include"bits/stdc++.h"
#define c std::cout<<
#define Q&a[0],&*end(a))
#define T;for(j=0;j<a.size()
int j,k;l(std::deque<int>a){auto p=[&]{c"["T;)c","+!j<<a[j++];c"]";};p();c"->";for(std::sort(Q;std::next_permutation(Q;){T-1;)if(a[j]==a[++j])goto e;c","+1/++k;p();e:;}k||c"[]";}

Try it online!

\$\endgroup\$
0
3
\$\begingroup\$

05AB1E, 5 bytes

œʒ¥ĀP

Includes duplicated items.

Try it online or verify all test cases.

Explanation:

œ      # Get all permutations of the (implicit) input-list
 ʒ     # Filter it by:
  ¥    #  Get the deltas/forward-differences
   Ā   #  Check for each whether it's NOT 0
    P  #  Product: check if all of them are truthy
       # (after which the result is output implicitly)

¥Ā could alternatively be üÊ for the same byte-count:

  ü    #  For each overlapping pair:
   Ê   #   Check that they are not equal
\$\endgroup\$
1
  • \$\begingroup\$ You're tied with the Vyxal answer! \$\endgroup\$
    – Joao-3
    Mar 16, 2022 at 17:53
2
\$\begingroup\$

Haskell, 69 bytes

import Data.List
f=(filter$and.(zipWith(/=)<*>tail)).nub.permutations

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 90 bytes

Returns a set of strings.

f=(a,p=[],s=new Set)=>a.map((v,i)=>v==p[0]||f(a.filter(_=>i--),[v,...p],s))+a?s:s.add(p+a)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 88 \$\endgroup\$
    – l4m2
    Mar 18, 2022 at 13:15
2
\$\begingroup\$

Ruby, 55 53 bytes

->l{[]|l.permutation.select{|r,*f|f.all?{|x|r!=r=x}}}

Try it online!

Thanks AZTECCO for -2 bytes

\$\endgroup\$
0
2
\$\begingroup\$

Python 3, 88 bytes

Thanks to user loopy walt for -7 bytes and user pxeger for -1 byte.
Returns a set of non-duplicate tuples. For the nothing case an empty set() is returned.

lambda l:{p for p in permutations(l)if p[:len([*groupby(p)])]==p}
from itertools import*

Attempt This Online!

Python 3.10, 95 bytes

Thanks to user LeopardShark for -1 byte.

lambda l:{p for p in permutations(l)if all(i!=j for i,j in pairwise(p))}
from itertools import*

Attempt This Online!

\$\endgroup\$
5
2
\$\begingroup\$

Jelly, 6 bytes

Œ!IẠ$Ƈ

Try it online!

How?

Œ!IẠ$Ƈ - Link: list of numbers, A
Œ!     - all permutations of A
     Ƈ - filter keep those for which:
    $  -   last two links as a monad:
  I    -     forward differences
   Ạ   -     all non-zero?
\$\endgroup\$
3
  • \$\begingroup\$ What do you mean by "duplicates"? \$\endgroup\$
    – Joao-3
    Mar 17, 2022 at 11:46
  • \$\begingroup\$ If the input is, say, [1, 1, 0] then the square-free permutations are [1,0,1] and [1,0,1] (where the two 1s are swapped). I added Q to match up with your examples which don't include these "repeats". Totally up to you whether we are allowed to include them or not... \$\endgroup\$ Mar 17, 2022 at 12:28
  • 1
    \$\begingroup\$ Ok, that's allowed. \$\endgroup\$
    – Joao-3
    Mar 26, 2022 at 14:44
2
\$\begingroup\$

Curry (PAKCS), 53 bytes

[]#s=s
(x++a:y)#s|s==[]||a/=head s=(x++y)#(a:s)
(#[])

Try it online!

Curry supports non-deterministic operations which can return different values for the same input. This is a non-deterministic function whose different return values are the all complex permutations (including duplicates).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.