Unsort an array

Question

_{Inspired by this StackOverflow post}

Given a list where each element appears a maximum of 2 times, we can define it's "sortedness" as the sum of the distances between equal elements. For example, consider

[1,1,2,3,3] (array)
 0 1 2 3 4  (indices)

The sortedness of this array is \$2\$. The distance between the 1s is \$1 - 0 = 1\$, the distance between the 2s is \$2 - 2 = 0\$ (as there's only one 2) and this distance between the 3s is \$4 - 3 = 1\$. Summing these distances, we get the sortedness as \$1 + 0 + 1 = 2\$.

Now, consider

[1,3,2,1,3] (array)
 0 1 2 3 4  (indices)

The sortedness of this array is \$6\$:

• 1s: \$3 - 0 = 3\$
• 2s: \$2 - 2 = 0\$
• 3s: \$4 - 1 = 3\$
• \$3 + 0 + 3 = 6\$

In fact, \$6\$ is the maximal sortedness of the permutations of this particular array, and there are 16 permutations of [1,1,2,3,3] with a sortedness of \$6\$.

[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]

---

Given a list of positive integers, where each integer appears either once or twice, output a permutation of this list where the sortedness is maximal. You may input and output in any convenient manner, and you may output any number of the permutations with maximal sortedness.

This is code-golf, so the shortest code in bytes wins.

Test cases

input -> output
[1] -> [1]
[8, 7] -> [8, 7]
[1, 1, 2] -> [1, 2, 1]
[9, 7, 4] -> [9, 7, 4]
[2, 9, 3, 10] -> [2, 9, 3, 10]
[4, 4, 10, 10] -> [4, 10, 4, 10]
[1, 1, 2, 3, 3] -> [1, 3, 2, 1, 3]
[2, 8, 5, 6, 5] -> [5, 2, 8, 6, 5]
[5, 2, 6, 1, 9] -> [5, 2, 6, 1, 9]
[7, 1, 1, 4, 5, 5, 8] -> [1, 5, 7, 4, 8, 1, 5]
[3, 1, 2, 8, 3, 10, 8] -> [3, 8, 1, 2, 10, 3, 8]
[1, 1, 2, 2, 3, 3, 4, 4] -> [1, 2, 3, 4, 1, 2, 3, 4]
[4, 4, 3, 3, 2, 2, 1, 1] -> [4, 3, 2, 1, 4, 3, 2, 1]

Answer 1

Python 3, 47 bytes

lambda l:(sorted({*l},key=l.count)*2)[-len(l):]

Try it online!

Answer 2

Python 2, 57 bytes

lambda l:[x for c in 1,2,1for x in set(l)if l.count(x)-c]

Try it online!

Iterates through the distinct elements of l 3 times, first outputting those that appear twice in l, then those that appear once, then twice again.

-1 byte by att

Python 3.8, 47 bytes

def f(l):*map(l.remove,s:={*l}),;l+=[*s-{*l}]+l

Try it online!

-3 bytes by pxeger with modifying the list in place

Answer 3

J, 10 bytes

/:~:*1#.e.

Try it online!

I had this first, hoping J might tie caird's Jelly, but I couldn't find any actual 9-byter.

How it works

/:~:*1#.e.    Monadic train, input: X, a numeric vector
     1#.e.    Count occurrences of each number of X in X
  ~:*         Multiply with nub sieve (1 if a number appears first, 0 otherwise)
              First occurrence of a double becomes 2, second becomes 0
              A single becomes 1
/:            Sort X by the above

Answer 4

Wolfram Language (Mathematica), 35 bytes

ReverseSort@Gather@#~Flatten~{2,1}&

Try it online!

                   #                    {1,1,2,3,3}
            Gather@                     {{1,1},{2},{3,3}}
ReverseSort@                            {{3,3},{1,1},{2}}
                    ~Flatten~{2  }      {{3,1,2},{3,1}}
                               ,1       {3,1,2,3,1}

Answer 5

Jelly, 7 bytes

ẹⱮ_"JỤị

Try it online!

How it works

ẹⱮ_"JỤị    Monadic link. Input: X, a numeric vector
ẹⱮ         For each element n of X, get all indices of n in X
  _"J      For each list of indices, subtract the original index
           If n appears twice, the first becomes [0, positive],
           and the second becomes [negative, 0].
           If n appears only once, it becomes [0].
     Ụị    Sort X by the above
           All [negative, 0]s come first, then [0]s, then [0, positive]s

I really hope Jelly were a proper derivative of J/K, in which case we wouldn't need the ".

Answer 6

Factor, ⁹⁴ 62 bytes

[ [ ] collect-by values [ length ] inv-sort-with round-robin ]

Have a screenshot of running this in Factor's REPL because collect-by postdates the build on TIO.

Explanation

I finally found a use for round-robin! It's sort of like if flip (matrix transposition) worked for non-rectangular matrices and it also flattens the results.

                          ! { 1 1 2 3 3 }
[ ] collect-by            ! H{ { 1 V{ 1 1 } } { 2 V{ 2 } } { 3 V{ 3 3 } } }
values                    ! { V{ 1 1 } V{ 2 } V{ 3 3 } }
[ length ] inv-sort-with  ! { V{ 1 1 } V{ 3 3 } V{ 2 } }
round-robin               ! { 1 3 2 1 3 }

Answer 7

Jelly, 6 bytes

ĠEÞZFị

A monadic Link accepting and returning a list of positive integers as specified.

Try it online!

How?

Produces a list of the form a+b+a where a is a list of the elements that are present twice and b is a list of the elements that only appear once. (a and b are also each sorted by value as a side effect of the method employed.)

ĠEÞZFị - Link: list of integers with at most two of each, A
                                             e.g. [3, 3, 1, 1, 2]
Ġ      - group indices of A by their values       [[3, 4], [5], [1, 2]]
  Þ    - sort the result using:                    v       v    v
 E     -   all equal?                              0       1    0
                                              ->  [[3, 4], [1, 2], [5]]
   Z   - transpose                                [[3, 1, 5], [4, 2]]
    F  - flatten                                  [3, 1, 5, 4, 2]
     ị - index back into A                        [1, 3, 2, 1, 3]

Answer 8

Jelly, 8 bytes

Œ!ĠISƊÐṀ

Try It Online!

Answer 9

Haskell + hgl, 17 bytes

cx<tx<rsB l<gr<sr

Explanation

This one is pretty simple, it composes 5 functions:

• sr sorts a list.
• gr groups a list into contiguous sublists of equal elements.
• rsB l sorts a list of lists in descending order of length.
• tx transposes a list of lists.
• cx concats a list of lists.

Worked example

We take the original list:

1 2 9 9 3 1

... sort it

1 1 2 3 9 9

... group it

1 1
2
3
9 9

... sort by length

1 1
9 9
2
3

... transpose it

1 9 2 3
1 9

.. and concat it

1 9 2 3 1 9

Reflections

This score seems pretty weak despite how straightforward the answer is. However I think there could be some improvements.

• rsB l and sB l could probably be their own functions. Sorting lists by length is likely to come up again so it would be nice to have these.
• gr<sr could probably be rolled into one function. It's not uncommon to want to get all the groups irrespective of the initial order and 5 bytes is a big price for that. Since the final order is arbitrary why not sort the output by size. It's the order we want here so that shows it's at least useful once.

As of e7ce5325 these changes have been implemented saving 9 bytes:

cx<tx<bg

Obviously this is non-competing, but these changes should be helpful in the future.

Answer 10

05AB1E, 7 bytes

ÙΣ¢}RI∍

Try it online!

-4 thanks to @ovs

Answer 11

MATL, 14 12 9 bytes

9B#u1>&)y

The input is a column vector. The output contains each entry on a line (not necessarily right-aligned). Try it online! Or verify all test cases.

Explanation

This outputs the duplicated numbers in their original order, then the non-duplicated numbers, then the duplicated numbers in their original order again.

9B   % Push 9, convert to binary. Gives [1 0 0 1]
#    % Use as output specification for the next function
u    % Implicit input. "Unique" function, first and fourth outputs. This
     % pushes the unique numbers in their orignal order, and their count
1>   % Greater than 1? (element-wise). Gives a mask for duplicated numbers
&    % Use alternative output specification for the next function
)    % Indexing, two outputs. This pushes the duplicated numbers, then the
     % non-duplicated numbers
y    % Duplicate from below. Implicit display

Answer 12

Python3, 139 131 116 106 bytes

def f(x):
 l,m=[],[]
 while x:
  i=x.pop()
  if x.count(i):l+=[i];x.remove(i)
  else:m+=[i]
 return l+m+l

Try it online

Alternative with lambda, 103 bytes

With non-deterministic ordering of elements. I'm not sure, whether that counts:

lambda x:(l:=[e for e in set(x)if x.count(e)>1])+[e for e in set(x)if x.count(e)<2]+l

Try it online

Answer 13

Python 3, 69 bytes

def f(l):x={z for z in l if l.count(z)<2};y=[*{*l}-x];return y+[*x]+y

Try it online!

No, @xnor has better version of this idea, heck @tsh has even better

Answer 14

J, 19 bytes

/:~:]`(I.@[)`[}1#.=

Try it online!

The idea is to create a mask for sorting, such that unique elements are pushed into the middle, and the first and second instances of repeat elements are pushed right and left, like a solution of water, oil, and mercury.

Consider 2 1 1 3 3:

• = Creates boolean masks for each unique element:

  1 0 0 0 0
  0 1 1 0 0
  0 0 0 1 1
  

• 1#. Sums the rows:

  1 2 2
  

• ~: Nub sieve of input: ones at the first occurrence of each element:

  1 1 0 1 0
  

• ]`(I.@[)`[} Update the nub sieve [ at the indices of those ones (I.@[) using the row-sum values ] (ie, 1 2 2):

  1 2 0 2 0
  

• /: Sort the original input according to that:

  1 3 2 1 3
  

Answer 15

Charcoal, 21 bytes

Ｗ⁻θυ⊞υ⊟ιＦ³ＩΦυ¬﹪⁻ι№θκ²

Try it online! Link is to verbose version of code. Explanation: Since each element is guaranteed to occur no more than twice, the exercise reduces to printing the elements that are duplicated, then the ones that only appear once, then the ones that are duplicated again.

Ｗ⁻θυ⊞υ⊟ι

Create a (reversed) deduplicated list of elements.

Ｆ³ＩΦυ¬﹪⁻ι№θκ²

Output the elements three times, but alternately filtered on whether the element was originally duplicated or not.

Answer 16

Vyxal, 13 bytes

ĠvḢf?Ġ'₃;fȮJJ

Try it Online! Wow this is a mess.

Ṗµ          ;t # Maximal permutation by...
  Uv=∩         # For each unique element, indices of equal elements?
      ƛ   ;∑   # Apply to each, taking the sum
       T       # Truthy indices
        ¯h     # Cumulative differences

Answer 17

Husk, 7 bytes

ΣT↔ÖLk=

Try it online!

Output is concatenation of:

1. List of all elements present, with those appearing twice coming first
2. List of elements that appear twice, in the same order as 1

     k=  # group list elements by equality
   ÖL    # and sort the groups by length
  ↔      # and reverse this order
         # (so now 2-element groups are first,
         # then 1-element groups),
 T       # now transpose
Σ        # and flatten the resulting list of 2 lists

Answer 18

R, 55 54 bytes

Edit: -1 byte thanks to Giuseppe

function(x)names(y<-table(x))[c(order(-y),which(y>1))]

Try it online!

Output as strings of the original elements. Add +3 bytes to output as the original elements themselves (see TIO link).

Output is: one of each element that appears twice, then elements that appear once, and finally one more of each element that appears twice.

Answer 19

BQN, 13 bytes

(⍷⍒∘⊒⊸⊏˜)∾⊒⊸/

Try it at BQN online REPL

         ∾      # join together:
(⍷⍒∘⊒⊸⊏˜)       # L: unique set of elements, with those present twice first
    ⊒           #    occurrence count of each element
  ⍒∘            #    reverse order (so those twice first)
      ⊸⊏˜       #    use this to index original elements
 ⍷              #    and deduplicate them;
          ⊒⊸/   # R: just the elements that are present twice
          ⊒     #    occurrence count of each element
           ⊸/   #    use this to select original elements

Answer 20

Vyxal, 13 bytes

Ṗµv=UvTv¯f∑;h

Try It Online!

Vyxal's deltas is negative for whatever reason, but no worries, we just get the minimum value then.

Answer 21

Retina 0.8.2, 53 44 bytes

O$`(\d+)((?<=\b\1,.*))?((?!.*,\1\b))?
$#2$#3

Try it online! Link includes test cases. Explanation: Saved 9 bytes by using @Bubbler's idea of encoding both whether the elements need to be sorted to the start or the end in the same sort key.

(\d+)

Matching each entry...

((?<=\b\1,.*))?

... check whether this is the second entry of a duplicate, and...

((?!.*,\1\b))?

... check whether this is a unique entry or the second entry of a duplicate.

O$`
$#2$#3

Sort by a combination of the two checks. The first entry of a duplicate has a sort key of 00. Unique elements have a sort key of 01. The second entry of a duplicate has a sort key of 11. This means that the unique elements sort between the two sets of duplicate elements.

Answer 22

Jelly, 7 bytes

A port of tsh's Python answer.

Qċ@Þ¹Uṁ

Try it online!

Q        -- the unique elements of the list
   Þ     -- sort by ...
 ċ@ ¹    --   the number of occurences in the full list 
     U   -- reverse
      ṁ  -- mold; reshape the list to the length of input by reusing from the front

Answer 23

python3, 121 101 bytes

def u(l):
 x=[]
 y=set()
 for i in l:x.append(i)if l.count(i)%2else y.add(i)
 y=list(y)
 return y+x+y

Try it online!

Thanks to caird coinheringaahing

Answer 24

Perl 5, 67 bytes

sub f{pop=~s/(.*)(\b\d+ )(.*)(\2)(.*)/my$x=$2;$x.f("$1$3$5").$x/er}

Try it online!

Answer 25

R, 48 bytes

function(x)c(d<-x[duplicated(x)],setdiff(x,d),d)

Try it online!

Answer 26

Ruby, 43 bytes

->l{(l&l-z=l.select{|x|l.count(x)<2})+z|=l}

Try it online!

Answer 27

Julia 1.0, 46 bytes

~a=(!x=a∩a[a.|>i->sum(i.==a)==x];[!2;!1;!2])

Try it online!

Answer 28

C (gcc), ^{119 \$\cdots\$ 103} 97 bytes

*b;*p;f(a,e)int*a,*e;{for(b=a;a<e;++a)for(p=a;++p<e;)*a==*p?*p^=*--e^(*e=*p),*a^=*b^(*b++=*a):0;}

Try it online!

Saved 3 bytes thanks to ceilingcat!!!

Inputs a pointer to an array of integers and a pointer one past the end of the array (because pointers in C carry no length info).
Unsorts the array in place.

Commented

*b;*p;f(a,e)int*a,*e;{             // declare pointers and f    
    for(   ;a<e;++a)               // main loop a to the end   
        b=a                        // init b to the beginning    
        for(p=a;++p<e;)            // inner loop of p from      
                                   //   a + 1 to the end
            *a==*p?                // is current int equal to  
                                   //   another int in a?    
                *p^=*  e^(*e=*p),  // then swap second int with  
                                   //   one before the end   
                     --            // move end back one    
                *a^=*b^(*b  =*a)   // and swap current int with   
                                   //   the beginning which   
                                   //   has already been seen   
                                   //   so is single or is the     
                                   //   same as what a points to     
                          ++       // bump up the beginning one   
            :0;                    // or do nothing    
}                                  //     

Answer 29

Vyxal, 56 bits^v2, 7 bytes

Þzµ≈;∩fİ

Try it Online!

Jelly porting ftw

Answer 30

JavaScript (Node.js), 60 bytes by tsh

a=>(p=a.filter(y=c=>!(y[c]^=1))).concat(a.filter(c=>y[c]),p)

Try it online!

JavaScript (Node.js), 61 bytes

x=>x.map(r=t=>r[t]=[r[t]?~++r[t][0]:4,t]).sort().map(t=>t[1])

Try it online!