Ordered list of binary sequences of multiple dimensions

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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}}

Answer 6

PHP, 49 bytes

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

Run with -r.

Answer 7

MATLAB, 68 bytes

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

Answer 8

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

Answer 9

Jelly, 14 bytes

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

Try it online!

Surprised this hadn't been posted yet.

Answer 10

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]²-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.

Answer 11

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