Complex permutation

Question

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 code-golf, 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>

Answer 1

Vyxal, 4 bytes

Ṗ'¯A

Try it Online!

Port of Jonathan Allan's Jelly answer.

-1 thanks to ovs.

Answer 2

J, 30 bytes

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

Try it online!

Answer 3

Haskell, 69 bytes

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

Try it online!

Answer 4

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.

Answer 5

BQN, 35 bytes^SBCS

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

Run online!

Answer 6

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.

Answer 7

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!

Answer 8

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

Answer 9

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!

Answer 10

Ruby, 55 53 bytes

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

Try it online!

Thanks AZTECCO for -2 bytes

Answer 11

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!

Answer 12

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?

Answer 13

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

Answer 14

Brachylog, 10 bytes

p.{s₂=}ᶜ0∧

A generator predicate that takes a list through its input parameter and produces permutations (including duplicates) through its output parameter. Try it online!

Explanation

p.{s₂=}ᶜ0∧
p           Get a permutation of the input list
 .          This is the output
  {   }ᶜ    Count the number of ways to:
   s₂        Get a length-2 sublist
     =       whose elements are equal
        0   Assert that the result is 0
         ∧  Don't try to unify 0 with the output

Answer 15

Scala, 162 bytes

Port of @G B's Ruby answer in Scala.

---

Golfed version. Try it online!

def u(l:List[Int])=l.permutations.filter(i).toList
def i(l:List[Int]):Boolean=l match{case Nil=>true case _::Nil=>true case x::y::xs=>if(x==y)false else i(y::xs)}

Ungolfed version. Try it online!

object Main {
  def uniquePermutations(list: List[Int]): List[List[Int]] = {
    list.permutations.filter(isUniqueConsecutive).toList
  }

  def isUniqueConsecutive(list: List[Int]): Boolean = {
    list match {
      case Nil => true
      case _::Nil => true
      case x::y::xs => if (x == y) false else isUniqueConsecutive(y::xs)
    }
  }

  def main(args: Array[String]): Unit = {
    println(uniquePermutations(List(0, 1, 1, 0)))
    println(uniquePermutations(List(1, 1, 1)))
  }
}

Answer 16

R, 93 bytes

\(v,m=permute::allPerms(v))for(i in 1:nrow(m)){l=v[m[i,]];if(all(l!=lag(l),na.rm=T))print(l)}

Prints in console, including duplicates:

v=c(0,-2,1,0) ; a(v)

[1] 0 -2 0 1
[1] 0 1 -2 0
[1] 0 1 0 -2
[1] -2 0 1 0
[1] -2 0 1 0
[1] 1 0 -2 0
[1] 1 0 -2 0
[1] 0 -2 0 1
[1] 0 -2 1 0
[1] 0 1 0 -2
[1] 0 1 -2 0

Answer 17

Uiua, 38 bytes

▽⊸≡(/×≡/≠◫2)∧(☇1⊞⍜⊙↻⊂¤⊙(⇡+1⊡1△.))⊙[[]]

Try it in the pad!

You can optionally add ◴ deduplicate to generate the solution without duplicates.