25
\$\begingroup\$

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 , 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]
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Related. Brownie points for beating/matching my 9 byte Jelly answer \$\endgroup\$ Dec 31 '21 at 0:01
  • \$\begingroup\$ Is it ok, if the lists are reversed, since this should not affect the distance? The last two examples suggest that it is not desired. \$\endgroup\$ Dec 31 '21 at 0:45
  • \$\begingroup\$ @RichardNeumann Yep, the reverse of the output is always a valid output, and the input being reversed as no effect (see the last two test cases), so that's fine, so long as it's consistent \$\endgroup\$ Dec 31 '21 at 0:47
  • \$\begingroup\$ Maybe it would be interesting to extend this challenge to inputs with number occurred more than 2 times by define sortedness as \$\sum_{i=1}^n\sum_{j=1}^n (a_i=a_j)\cdot|i-j|\$. \$\endgroup\$
    – tsh
    Dec 31 '21 at 5:29
  • \$\begingroup\$ @tsh I was considering extending it beyond 2 times, but I wasn't sure on an obvious extension (for three equal items, do you take the three distances between them, or the distances between the first and second, and second and third?), and keeping with 2 times was more fitting with the original SO post \$\endgroup\$ Dec 31 '21 at 5:40

29 Answers 29

14
\$\begingroup\$

Python 3, 47 bytes

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

Try it online!

\$\endgroup\$
2
  • 3
    \$\begingroup\$ This is an amazingly elegant solution. \$\endgroup\$ Dec 31 '21 at 3:59
  • 1
    \$\begingroup\$ I would really love an explanation for why this produces a maximum sortedness \$\endgroup\$
    – Gulzar
    Jan 2 at 8:50
13
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ -3 by updating l in-place with +=: Try it online! \$\endgroup\$
    – pxeger
    Dec 31 '21 at 1:36
  • \$\begingroup\$ invert c for -1 \$\endgroup\$
    – att
    Dec 31 '21 at 1:37
  • \$\begingroup\$ 47 but as lambda: lambda l:l+[*(s:={*l})-{*map(l.remove,s),*l}]+l \$\endgroup\$
    – tsh
    Jan 1 at 0:42
10
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Wow, I really thought I had found the shortest. At least it's the same basic idea :). And TIL about monadic e., which I don't think I've ever used. \$\endgroup\$
    – Jonah
    Dec 31 '21 at 2:36
  • \$\begingroup\$ @Jonah When used on flat arrays, e. is equivalent to =/~. \$\endgroup\$
    – Bubbler
    Dec 31 '21 at 2:42
  • \$\begingroup\$ Ah, right. I should have seen that. In any case I suspect there are bytes to be saved with monadic e. in some of my past golfs. \$\endgroup\$
    – Jonah
    Dec 31 '21 at 2:43
8
\$\begingroup\$

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}
\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

Factor, 94 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.

enter image description here

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 }
\$\endgroup\$
2
  • \$\begingroup\$ Nice. Out of curiosity what does the V mean and why doesn’t the input have it? \$\endgroup\$
    – Jonah
    Dec 31 '21 at 18:13
  • 1
    \$\begingroup\$ @Jonah In Factor { } (arrays) are fixed-size mutable sequences while V{ } (vectors) are resizeable mutable sequences. Some words, such as collect-by end up collecting indefinite amounts of things in vectors for efficiency. But these are both instances of sequence and almost every sequence word can be used on both. \$\endgroup\$
    – chunes
    Dec 31 '21 at 21:23
6
\$\begingroup\$

Jelly, 8 bytes

Œ!ĠISƊÐṀ

Try It Online!

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 7 bytes

ÙΣ¢}RI∍

Try it online!

-4 thanks to @ovs

\$\endgroup\$
4
  • \$\begingroup\$ .γ¢}Ć˜ can be shortened to I∍. In this case behaves like Jelly's ṁold. \$\endgroup\$
    – ovs
    Dec 31 '21 at 10:29
  • \$\begingroup\$ ^ do this nooow \$\endgroup\$
    – Fmbalbuena
    Dec 31 '21 at 13:51
  • \$\begingroup\$ @ovs thanks! mold builtin was hard to find \$\endgroup\$
    – wasif
    Dec 31 '21 at 16:35
  • \$\begingroup\$ @Fmbalbuena done! Sorry for being lazy \$\endgroup\$
    – wasif
    Dec 31 '21 at 16:35
5
\$\begingroup\$

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]
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Javascript (ES6), 63 bytes

f=([a,...x],y=x.pop())=>x[0]?[a,...f(x.reverse()),y]:y?[a,y]:[a]

f=([a,...x],y=x.pop())=>x[0]?[a,...f(x.reverse()),y]:y?[a,y]:[a]

console.log(f([1,1,2,3,3]))
console.log(f([4,4,10,10]))

A quite neat recursive function. Takes input sorted.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ l,m=[],[] can be l=m=[] \$\endgroup\$
    – Fmbalbuena
    Dec 31 '21 at 13:52
  • 1
    \$\begingroup\$ No. This would make l and m the same list. And since the += operator modifies the list in-place, it would modify "both" lists: a=b=[];print(a,b);a+=[1];print(a,b) \$\endgroup\$ Dec 31 '21 at 13:57
  • \$\begingroup\$ Ok, Or l=[];m=l? \$\endgroup\$
    – Fmbalbuena
    Dec 31 '21 at 14:01
  • 1
    \$\begingroup\$ Same issue... Try it. a=[];b=a;print(a,b);a+=[1];print(a,b) \$\endgroup\$ Dec 31 '21 at 14:02
  • \$\begingroup\$ Ok, thanks Richard. \$\endgroup\$
    – Fmbalbuena
    Dec 31 '21 at 14:02
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
    
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 21 bytes

W⁻θυ⊞υ⊟ιF³IΦυ¬﹪⁻ι№θκ²

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.

W⁻θυ⊞υ⊟ι

Create a (reversed) deduplicated list of elements.

F³IΦυ¬﹪⁻ι№θκ²

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

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

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Trivial 1-byte golf by in-lining the assignment of y in the names(). \$\endgroup\$
    – Giuseppe
    Jan 2 at 1:07
  • \$\begingroup\$ @Giuseppe - Ah, yes, thanks. \$\endgroup\$ Jan 2 at 9:33
3
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Instead of joining to the elements occurring twice, you can reshape the unique set to the length of the input. ≠⥊·⍷⍒∘⊒⊸⊏˜ works for 10 \$\endgroup\$
    – ovs
    Jan 4 at 15:12
2
\$\begingroup\$

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.

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

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.

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

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
\$\endgroup\$
1
  • \$\begingroup\$ The ċ@Þ¹ to sort by the number of occurrences feels very long, and sorting the full list before taking the unique items doesn't seem to help (ċ@Þ`QUṁ) \$\endgroup\$
    – ovs
    Dec 31 '21 at 10:44
2
\$\begingroup\$

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

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

Perl 5, 67 bytes

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

Try it online!

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

R, 48 bytes

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

Try it online!

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

Ruby, 43 bytes

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

Try it online!

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

Julia 1.0, 46 bytes

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

Try it online!

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

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    
}                                  //     
\$\endgroup\$
0

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.