# Shuffle string of digits

## Challenge

You have been given a string of digits 0-9.1 Your task is to shuffle this string, but every index must have a different value than it did before the string was shuffled.

For example:

In : 287492
Out: 892247


If this is not possible, return false or something similar. (null, undefined, etc.)

In : 131
Out: false


There is no upper bound on the length of the string, but you can assume you have unlimited computation time.

Your function must pass the following tests:

shuffle('2')                   => false
shuffle('88')                  => false
shuffle('794588888')           => false
shuffle('344999')              => for example, '999434'
shuffle('172830560542976539')  => for example, '271038650425697395'


Shortest code wins, and good luck!

1 More specifically, the string would match /^[0-9]+$/. • so, you are asking for derangements... – J42161217 May 14 at 21:02 • @mathjunkie, both of those things you proposed would be allowed. Sorry for the late response. – applemonkey496 May 14 at 23:18 • Closely related – Luis Mendo May 15 at 0:32 • @Kevin I’m not sure, because this challenge doesn’t seem to require random output, i.e. it can be deterministic (it’s not clear to me from the challenge specification) – Luis Mendo May 15 at 10:10 • @LuisMendo also this question asks a falsey output when not possible, in the other question it assumes the input is possible, as for exemple the PHP answer (that I noticed only after having posted mine, but has same approach) will be stuck in an infinite loop. And it's a non negligeable part of the answer's length in mine – Kaddath May 15 at 13:09 ## 9 Answers # Jelly, 6 bytes Œ!nẠ¥Ƈ  Try it online! # K (ngn/k), 37 32 bytes {$[|/x=r:x[,/|2 0N#<x]@<<x;0;r]}


Try it online!

{ } function with argument x

$[ ; ; ] if-then-else <x "grade" - the sorting permutation for x <<x "rankings" - the inverse of the sorting permutation 2 0N# split in two halves (or when length is odd - only approximately) | swap the halves ,/ concatenate x[ ] use as indices in x ..@<<x use <<x as indices in the previous result (a@b is alternative syntax for a[b]) r: assign to r - the potential result x=r boolean list of which elements of x are equal to their counterparts in r |/ or-reduction, i.e. "any?" • How does it work? Just curious :) – applemonkey496 May 14 at 21:21 • @applemonkey496 i'll explain a bit later. i'm still looking for ways to shorten it. generally: sort, rotate by the size of the largest group, and unsort. – ngn May 14 at 21:23 • i changed the algorithm slightly - now rotation is by half the length of x – ngn May 14 at 21:50 • Neat approach. So is it looping or doing any recursion, or just checking 2 possibilties. I'm still a little fuzzy even with the explanation. – Jonah May 15 at 1:00 • @Jonah no, there's no looping or recursion. i'm not good at explanations, is there anything in particular that should be rephrased? – ngn May 15 at 12:06 # 05AB1E, 7 bytes Like the Pyth answer, outputs all possible shuffled strings or digits. œʒø€Ëà_  Try it online! ## Explanation œ Permutations of the input ʒ Filter such that: ø Zipping with the original input €Ë And comparing at corresponding indices à_ are all unequal.  • This one is shorter now, so I made it the winner (so far) :) – applemonkey496 May 15 at 18:01 • I think œ is permutations, not powerset – math junkie May 15 at 20:45 # Pyth, 9 bytes f.AnVQT.p  Try it online! Outputs all possible strings that meet the criteria given in the question. This results in an empty list for the false cases. # Pyth, 7 bytes -VI#Q.p  Try it online! Takes input as a list of digit-characters. For example: ['1', '2', '3']  Output: all possible derangements, with multiplicity for related characters. • .p: Generate all permutations. • #: Filter on • I: Invariant under • -V ... Q: Removing all characters that are at the same position in the input. # JavaScript (Node.js), 125 bytes e=>[...Array(i=2+e|0)].every(_=>(s=[...q=(--i+'').slice(1)]).some((_,j)=>_==e[j])|s.sort()+''!=[...e].sort()||console.log(q))  Try it online! # Python 2, 83 80 bytes lambda l:[p for p in permutations(l)if all(map(cmp,l,p))] from itertools import*  Try it online! Goes through all permutation of the string, and keeps the ones that are different to the original string at every index. • You should be able to drop the  since outputting all possible strings is now allowed – math junkie May 14 at 23:33 • Fun fact: my pyth solution translates almost directly to your solution – math junkie May 14 at 23:35 • @mathjunkie The generation output of the Pyth solution generates exactly this solution, byte-for-byte? – user92069 May 15 at 6:56 • @Λ̸̸ Not quite (eg. cmp vs. n which would be != in Python). But I imagine the generated code would be quite similar – math junkie May 15 at 16:03 # PHP, 152 141 bytes $a=count_chars($s=$argn,1);rsort($a);$a*2<=strlen($s)?:die;for($s=$t=str_split($s);$s!=array_diff_assoc($s,$t);)shuffle($t);echo join(\$t);


Try it online!

A bit lengthy but it's my first approach, will think more about it later

• displays empty string (exits) if impossible (if the most frequent number occurence is more than half of length of the string)
• uses an array approach and shuffles until it finds a proper result

EDIT: fixed an error in string length var attribution (missing brackets) + improved while condition for +1 byte

EDIT2: saved 1 byte, since brackets were mandatory for ternary condition, an if is now shorter

EDIT3: saved 11 bytes with the help of this answer by Titus to a closely related question

# JavaScript (Node.js), 187 bytes

e=>{for(b=a=e.slice().sort(),a=+a.join(""),b=+b.reverse().join("");a<=b;){if(k=(a+"").split("").map(a=>+a),b==k.slice().sort((a,e)=>e-a).join("")&&e.every((a,e)=>a!=+k[e]))return a;a++}}



Try it online!

-8 bytes thanks VFDan

# JavaScript (Node.js), 179 bytes

e=>{for(b=a=e.slice().sort(),a=+a.join,b=+b.reverse().join;a<=b;){if(k=(a+"").split.map(a=>+a),b==k.slice().sort((a,e)=>e-a).join&&e.every((a,e)=>a!=+k[e]))return a;a++}}



Try it online!

• You can save 8 bytes by turning all ("") to : e=>{for(b=a=e.slice().sort(),a=+a.join,b=+b.reverse().join;a<=b;){if(k=(a+"").split.map(a=>+a),b==k.slice().sort((a,e)=>e-a).join&&e.every((a,e)=>a!=+k[e]))return a;a++}} – VFDan May 17 at 19:04
• Nice, Thank you for trick!!! – Yaroslav Gaponov May 17 at 20:34