8
\$\begingroup\$

Given a positive integer n, output the 2^n binary sequences of length n sorted in the following precise ordering.

Test cases:

0:

0 or 1 (defining this is a matter of debate)

1:

0
1

2:

00
01
10
11

3:

000
001
010
100
011
101
110
111

4:

0000
0001
0010
0100
1000
0011
0101
1001
0110
1010
1100
0111
1011
1101
1110
1111

etc.

Additionally, the pattern of combinatorics is related to Pascal's Triangle.

0:

1 (this is given regardless of the definition given to 2^0)

1:

1
1

2:

1
2
1

3:

1
3
3
1

4:

1
4
6
4
1

etc.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ For me above could be the result of one bug in a sorting algo... \$\endgroup\$
    – user58988
    Nov 22, 2016 at 11:26

11 Answers 11

3
\$\begingroup\$

Haskell, 78 bytes

import Data.List
f n=sortOn(\x->sum x:reverse(map(1-)x))$mapM id$[0,1]<$[1..n]

Usage example: f 2 -> [[0,0],[0,1],[1,0],[1,1]].

How it works:

         [0,1]<$[1..n]  -- make n copies of the list [0,1]
     mapM id            -- make all lists where the ith element is from the ith list.
                        -- that gives us all binary sequences
sortOn                  -- sort this list of list
    sum x               -- first by number of ones
      reverse(map(1-)x) -- then by the reversed list with bits flipped
\$\endgroup\$
4
  • \$\begingroup\$ I used a Haskell compiler from the Apple Store, and I'm not sure if that won't allow me to run this code. Took a screenshot of what happens when I run it: m.imgur.com/VIByUah \$\endgroup\$
    – defarm
    Nov 4, 2016 at 2:43
  • \$\begingroup\$ @DreadVim: it seems that you don't have the latest version of the libraries (Prelude for <$ and Data.List for sortOn). Also: my code isn't a full program, so it won't compile. \$\endgroup\$
    – nimi
    Nov 4, 2016 at 3:02
  • \$\begingroup\$ Ah. That makes sense. I'll have to do it on my laptop. \$\endgroup\$
    – defarm
    Nov 4, 2016 at 3:15
  • \$\begingroup\$ TIL about sortOn. I will miss sortBy (compare `on` f). \$\endgroup\$
    – Angs
    Nov 4, 2016 at 11:42
2
\$\begingroup\$

Python 2, 146 bytes

from itertools import*
lambda i:sum([sorted({''.join(b)for b in permutations((i-n)*"0"+"1"*n)},key=lambda x:x[::-1])[::-1]for n in range(i+1)],[])

I'm still working on this, though any suggestions would be greatly appreciated!

Ungolfed

i=input()   
import itertools
p=[]
for n in range(i+1):
    x=(i-n)*"0"+"1"*n
    t=[]
    for b in itertools.permutations(x):t+=[''.join(b)] if ''.join(b) not in t else []
    p.append(sorted(t, key=lambda x:x[::-1])[::-1])

p=sum(p,[])
print
for line in p:print line
\$\endgroup\$
1
  • \$\begingroup\$ do from itertools import* and then just use permutations in the lambda. saves 1 byte \$\endgroup\$
    – FlipTack
    Nov 5, 2016 at 20:44
1
\$\begingroup\$

Python 2, 122 120 102 98 bytes

18 bytes saved thanks to Flp.Tkc

4 bytes saved thanks to xnor

lambda x:sorted([bin(i)[2:].zfill(x)for i in range(2**x)],key=lambda x:(sorted(x),int(x[::-1],2)))

Explanation

This makes all the binary strings of length x with:

[bin(i)[2:].xfill(x)for i in range(2**x)]

I then sort them according to:

lambda x:(sorted(x),int(x[::-1],2))

sorted(x) prioritizes the number of 1s while int(x[::-1],2) prioritizes the second condition

Lastly these are joined with newlines and printed.

\$\endgroup\$
10
  • \$\begingroup\$ This is not eligible. \$\endgroup\$
    – defarm
    Nov 3, 2016 at 3:50
  • \$\begingroup\$ @DreadVim It is now \$\endgroup\$
    – Wheat Wizard
    Nov 3, 2016 at 3:55
  • \$\begingroup\$ Agreed. Good job. \$\endgroup\$
    – defarm
    Nov 3, 2016 at 3:56
  • \$\begingroup\$ This seems to trim leading zeroes. \$\endgroup\$
    – xnor
    Nov 3, 2016 at 6:42
  • \$\begingroup\$ The 106 byte version seems to give a different order for n=4. Yours gives 0110 then 1001, which is switched fro the test case. I'm not sure how the correct order is actually specified. \$\endgroup\$
    – xnor
    Nov 3, 2016 at 6:46
1
\$\begingroup\$

Perl, 63 bytes

-4 thanks to @Ton Hospel.
-2 thanks to @Gabriel Benamy.

say~~reverse for sort{$b=~y/0//-$a=~y/0//||$b-$a}glob"{1,0}"x<>

Run with -E (which enable the feature say) :

perl -E 'say~~reverse for sort{$b=~y/0//-$a=~y/0//||$b-$a}glob"{1,0}"x<>' <<< 5


Short explanations:

  • "{1,0}"x$_ creates a string composed of $_ times{1,0} ($_ is the input). For instance with 3 : {1,1}{1,0}{1,0}.
  • Then glob does some magic and generates all combinations of one element from each group of braces (that is, all the combinations we want to print).
  • And then the sort : $b=~y/1//c-$a=~y/1//c compares the number of 1 in each string, and if they have the same number, $b-$a will sort according to the second rule.
\$\endgroup\$
4
  • \$\begingroup\$ I believe you can save two bytes by changing y/1//c to y/0// both times \$\endgroup\$ Nov 6, 2016 at 0:08
  • \$\begingroup\$ @GabrielBenamy Indeed, thanks. I'm too used to use y///c! \$\endgroup\$
    – Dada
    Nov 6, 2016 at 0:20
  • \$\begingroup\$ Replace <=> by - \$\endgroup\$
    – Ton Hospel
    Nov 6, 2016 at 9:28
  • \$\begingroup\$ @TonHospel edited, thanks! \$\endgroup\$
    – Dada
    Nov 6, 2016 at 9:34
0
\$\begingroup\$

Perl, 116 106 105 102 bytes

sub e{sprintf"%0$%b",@_}sub f{$_=e@_;/0*$/;$%*y/1//-$-[0]}map{say e$_}sort{f($a)<=>f$b}0..2**($%=<>)-1

Readable:

sub e{
    sprintf"%0$%b",@_
}
sub f{
    $_=e@_;/0*$/;$%*y/1//-$-[0]
}
map{
    say e$_
} sort {
    f($a)<=>f$b
} 0..2**($%=<>)-1

The subroutine e converts its argument into a binary value, padded with zeros, to be the input length (e.g. input of 5 pads with zeros until it's 5 characters long). The subroutine f takes such a binary value, and gives it sorting weight according to how it should be processed.

The range 0 .. [input]2-1 is then put through a stable sort, ordering by the weight (here, "stable" means that when two values have the same weight, they are returned in the same order they appear in the input), and then they are fed back to the subroutine e and output.

Some of you may have seen my original post, but I entirely misread the problem yesterday and deleted it immediately after I realized it.

\$\endgroup\$
1
  • \$\begingroup\$ This doesn't produce the require output for n>=5. For instance, with n>=5, 01101 comes before 10011 but it should be after. \$\endgroup\$
    – Dada
    Nov 5, 2016 at 23:56
0
\$\begingroup\$

Racket 109 bytes

(let loop((s ""))(if(= n(string-length s))(displayln s)(for((i '("0" "1")))(loop(string-append s i)))))

Ungolfed:

(define (f n)
  (let loop ((s ""))
    (if (= n (string-length s))
        (displayln s)
        (for ((i '("0" "1")))
          (loop (string-append s i))))))

Testing:

(f 2)
(println "-------------")
(f 3)
(println "-------------")
(f 4)

Output:

00
01
10
11
"-------------"
000
001
010
011
100
101
110
111
"-------------"
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
\$\endgroup\$
2
  • 1
    \$\begingroup\$ In case n=3 above is not the same to exercise text 000 001 010 100 etc \$\endgroup\$
    – user58988
    Nov 22, 2016 at 9:01
  • \$\begingroup\$ This exercise would be about to write the right function for to sort a list of numbers (and than print the binary form) \$\endgroup\$
    – user58988
    Nov 22, 2016 at 9:14
0
\$\begingroup\$

Ruby 2.x, 129 bytes

f=->(n){z='0';p=n.bit_length;(0..n).map{|i|sprintf("%0#{p}d",i.to_s(2))}.sort{|a,b|a=a.delete(z).size-(b=b.delete(z).size)||b-a}}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! Unfortunately, this doesn't quite seem to do what the challenge asks for. For example, input 5 prints the first five lines of the output that corresponds to 3. \$\endgroup\$
    – Dennis
    Nov 22, 2016 at 3:52
0
\$\begingroup\$

PHP, 49 bytes

while($i<1<<$n=$argv[1])printf("%0${n}b\n",$i++);

Run with -r.

\$\endgroup\$
0
\$\begingroup\$

MATLAB, 68 bytes

d=@(n)dec2bin(sortrows([sum(dec2bin(0:2^n-1)');0:2^n-1]')*~eye(2,1))
\$\endgroup\$
0
\$\begingroup\$

Bash, 65 bytes

Golfed

seq -f "obase=2;%g+2^$1-1" $[2**$1]|bc|cut -c2-|tr 0 ~|sort|tr ~ 0

Test

>./binseq 4

0000
0001
0010
0100
1000
0011
0101
0110
1001
1010
1100
0111
1011
1101
1110
1111
\$\endgroup\$
6
  • \$\begingroup\$ It is wrong... I copy and paste the above output:0011 0101 1001 0110 1010 1100 after 0101 there is 1001 and not 0110 \$\endgroup\$
    – user58988
    Dec 2, 2016 at 15:34
  • \$\begingroup\$ Indeed it does imgur.com/a/yxBLp, my guess, is that you are probably just running a system with a different locale (I use "en_US.UTF-8"), so the different collation rules apply (which is an expected and documented "sort" behavior). Try changing the locale, or tell me yours, and I will see which char you should use in place of ~. \$\endgroup\$
    – zeppelin
    Dec 2, 2016 at 18:49
  • \$\begingroup\$ Another thing you may try is to enforce the dictionary order on sort with "-d" (that should produce less locale specific results) \$\endgroup\$
    – zeppelin
    Dec 2, 2016 at 18:52
  • \$\begingroup\$ i say your result print above for n=4 [0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111] is different from the result of the question for n=4 [0000 0001 0010 0100 1000 0011 0101 1001 0110 1010 1100 0111 1011 1101 1110 1111] infact the 9th position of that array has one different value \$\endgroup\$
    – user58988
    Dec 2, 2016 at 21:57
  • \$\begingroup\$ @RosLup I believe 0101 => 1001 is an error in test case data, not my implementation, see discussion on the "Python 2" answer below: "Yours gives 0110 then 1001, which is switched fro the test case. I'm not sure how the correct order is actually specified. – xnor" "My mistake. It's actually flipped ... - Dread Vim" (the OP) \$\endgroup\$
    – zeppelin
    Dec 2, 2016 at 22:07
0
\$\begingroup\$

Jelly, 14 bytes

2Ḷṗ⁸TṪ$N$ÞSÞYȯ

Try it online!

Surprised this hadn't been posted yet.

\$\endgroup\$

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.