14
\$\begingroup\$

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]+$/.

\$\endgroup\$
16
  • 5
    \$\begingroup\$ so, you are asking for derangements... \$\endgroup\$
    – ZaMoC
    May 14, 2020 at 21:02
  • 1
    \$\begingroup\$ @mathjunkie, both of those things you proposed would be allowed. Sorry for the late response. \$\endgroup\$ May 14, 2020 at 23:18
  • 1
    \$\begingroup\$ Closely related \$\endgroup\$
    – Luis Mendo
    May 15, 2020 at 0:32
  • 1
    \$\begingroup\$ @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) \$\endgroup\$
    – Luis Mendo
    May 15, 2020 at 10:10
  • 2
    \$\begingroup\$ @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 \$\endgroup\$
    – Kaddath
    May 15, 2020 at 13:09

9 Answers 9

6
\$\begingroup\$

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?"

\$\endgroup\$
9
  • \$\begingroup\$ How does it work? Just curious :) \$\endgroup\$ May 14, 2020 at 21:21
  • \$\begingroup\$ @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. \$\endgroup\$
    – ngn
    May 14, 2020 at 21:23
  • \$\begingroup\$ i changed the algorithm slightly - now rotation is by half the length of x \$\endgroup\$
    – ngn
    May 14, 2020 at 21:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jonah
    May 15, 2020 at 1:00
  • \$\begingroup\$ @Jonah no, there's no looping or recursion. i'm not good at explanations, is there anything in particular that should be rephrased? \$\endgroup\$
    – ngn
    May 15, 2020 at 12:06
6
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ I think œ is permutations, not powerset \$\endgroup\$ May 15, 2020 at 20:45
3
\$\begingroup\$

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.

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

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.

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

Jelly, 6 bytes

Œ!nẠ¥Ƈ

Try it online!

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

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You should be able to drop the [0] since outputting all possible strings is now allowed \$\endgroup\$ May 14, 2020 at 23:33
  • 1
    \$\begingroup\$ Fun fact: my pyth solution translates almost directly to your solution \$\endgroup\$ May 14, 2020 at 23:35
  • \$\begingroup\$ @mathjunkie The generation output of the Pyth solution generates exactly this solution, byte-for-byte? \$\endgroup\$
    – user92069
    May 15, 2020 at 6:56
  • \$\begingroup\$ @Λ̸̸ Not quite (eg. cmp vs. n which would be != in Python). But I imagine the generated code would be quite similar \$\endgroup\$ May 15, 2020 at 16:03
1
\$\begingroup\$

PHP, 152 141 bytes

$a=count_chars($s=$argn,1);rsort($a);$a[0]*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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 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++}} \$\endgroup\$
    – VFDan
    May 17, 2020 at 19:04
  • \$\begingroup\$ Nice, Thank you for trick!!! \$\endgroup\$ May 17, 2020 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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