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

Jelly, 6 bytes

Œ!nẠ¥Ƈ

Try it online!

| improve this answer | |
\$\endgroup\$
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?"

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ How does it work? Just curious :) \$\endgroup\$ – applemonkey496 May 14 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 at 21:23
  • \$\begingroup\$ i changed the algorithm slightly - now rotation is by half the length of x \$\endgroup\$ – ngn May 14 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 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 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.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This one is shorter now, so I made it the winner (so far) :) \$\endgroup\$ – applemonkey496 May 15 at 18:01
  • \$\begingroup\$ I think œ is permutations, not powerset \$\endgroup\$ – math junkie May 15 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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You should be able to drop the [0] since outputting all possible strings is now allowed \$\endgroup\$ – math junkie May 14 at 23:33
  • 1
    \$\begingroup\$ Fun fact: my pyth solution translates almost directly to your solution \$\endgroup\$ – math junkie May 14 at 23:35
  • \$\begingroup\$ @mathjunkie The generation output of the Pyth solution generates exactly this solution, byte-for-byte? \$\endgroup\$ – user92069 May 15 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\$ – math junkie May 15 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

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
  • \$\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 at 19:04
  • \$\begingroup\$ Nice, Thank you for trick!!! \$\endgroup\$ – Yaroslav Gaponov May 17 at 20:34

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.