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
    \$\begingroup\$ For me above could be the result of one bug in a sorting algo... \$\endgroup\$ – RosLuP Nov 22 '16 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\$
  • \$\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\$ – David E. Farmilant Nov 4 '16 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 '16 at 3:02
  • \$\begingroup\$ Ah. That makes sense. I'll have to do it on my laptop. \$\endgroup\$ – David E. Farmilant Nov 4 '16 at 3:15
  • \$\begingroup\$ TIL about sortOn. I will miss sortBy (compare `on` f). \$\endgroup\$ – Angs Nov 4 '16 at 11:42
1
\$\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\$
  • \$\begingroup\$ do from itertools import* and then just use permutations in the lambda. saves 1 byte \$\endgroup\$ – FlipTack Nov 5 '16 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\$
  • \$\begingroup\$ This is not eligible. \$\endgroup\$ – David E. Farmilant Nov 3 '16 at 3:50
  • \$\begingroup\$ @DreadVim It is now \$\endgroup\$ – Sriotchilism O'Zaic Nov 3 '16 at 3:55
  • \$\begingroup\$ Agreed. Good job. \$\endgroup\$ – David E. Farmilant Nov 3 '16 at 3:56
  • \$\begingroup\$ This seems to trim leading zeroes. \$\endgroup\$ – xnor Nov 3 '16 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 '16 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\$
  • \$\begingroup\$ I believe you can save two bytes by changing y/1//c to y/0// both times \$\endgroup\$ – Gabriel Benamy Nov 6 '16 at 0:08
  • \$\begingroup\$ @GabrielBenamy Indeed, thanks. I'm too used to use y///c! \$\endgroup\$ – Dada Nov 6 '16 at 0:20
  • \$\begingroup\$ Replace <=> by - \$\endgroup\$ – Ton Hospel Nov 6 '16 at 9:28
  • \$\begingroup\$ @TonHospel edited, thanks! \$\endgroup\$ – Dada Nov 6 '16 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\$
  • \$\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 '16 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\$
  • 1
    \$\begingroup\$ In case n=3 above is not the same to exercise text 000 001 010 100 etc \$\endgroup\$ – RosLuP Nov 22 '16 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\$ – RosLuP Nov 22 '16 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\$
  • 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 '16 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\$
  • \$\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\$ – RosLuP Dec 2 '16 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 '16 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 '16 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\$ – RosLuP Dec 2 '16 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 '16 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.