18
\$\begingroup\$

... Ah sorry, no popcorn here, just POPCNT.

Write the shortest program or function which takes in a number n and output all integers from 0 to 2n - 1, in ascending order of number of 1 bits in the binary representation of the numbers (popcount). No duplicates allowed.

The order of numbers with the same popcount is implementation-defined.

For example, for n = 3, all these output are valid:

0, 1, 2, 4, 3, 5, 6, 7
[0, 4, 1, 2, 5, 3, 6, 7]
0 4 2 1 6 5 3 7 

The input and output format are implementation-defined to allow the use of language features to further golf the code. There are a few restrictions on the output:

  • The numbers must be output in decimal format.
  • The output must contain a reasonable separator between the numbers (trailing separator allowed, but not leading).

    Line feed (\n), tab (\t), space, ,, ., ;, |, -, _, / are quite reasonable separator. I don't mind additional spaces for pretty printing, but don't use letter or digits as separators.

  • The numbers and separators can be surrounded by [ ], { } or any array or list notation.
  • Don't print anything else not stated above.

Bonus

Multiply your score by 0.5 if your solution can generate the number on the fly. The spirit of this bonus is that if you were to directly convert your printing solution to a generator, the generator only uses at most O(n) memory where n is the number of bits as defined above. (You don't have to actually convert your solution to generator). Note that while I impose n <= 28, the memory needed to store all numbers still grows exponentially, and a naive sorting solution would hog up at least 4 GB of memory at n = 28.

Please add some simple explanation of how your solution works before claiming this bonus.

\$\endgroup\$
  • 4
    \$\begingroup\$ It seems that the challenge as it is quite boring and would result in a bunch of sorting answers. I would like to add some bonus to make the challenge more interesting. Something along the line of "generating the numbers on the fly". If you are OK with it, please upvote this comment, then I will add it to the question. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 27 '15 at 5:29
  • \$\begingroup\$ If you disagree, please upvote this comment. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 27 '15 at 5:30
  • \$\begingroup\$ Please use the sandbox to ask for further suggestions on a question before posting it live. \$\endgroup\$ – John Dvorak Feb 27 '15 at 7:30
  • 21
    \$\begingroup\$ @JanDvorak: It was on sandbox for one month. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 27 '15 at 7:59
  • 1
    \$\begingroup\$ I think it's too late for this question. Generally, questions where you have to figure out a non-trivial algorithm aren't well suited for code golf in my opinion. Make them a code challenge instead and pose all the constraints you need. \$\endgroup\$ – FUZxxl Feb 28 '15 at 2:48

15 Answers 15

10
\$\begingroup\$

Pyth, 9 bytes

osjN2U^2Q

order by the sum of the base 2 representation (jN2) over the range (U) of 2 ^ Q.

(Q = eval(input())).

Try it here.

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

Python 2, 75 * 0.5 = 37.5

N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.

Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.

Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.

Output for 4:

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15
\$\endgroup\$
  • \$\begingroup\$ There is no need for the number with the same popcount to be increasing. The order is implementation-defined. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 27 '15 at 9:47
  • 1
    \$\begingroup\$ @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ I'm aware, but I don't see how to save characters doing it differently. \$\endgroup\$ – xnor Feb 27 '15 at 9:48
  • \$\begingroup\$ With a naive 3 loops method, I score almost the same in JS (having console.log() vs print). Maybe the bit trick is too heavy. \$\endgroup\$ – edc65 Feb 27 '15 at 11:12
  • \$\begingroup\$ One byte saving: v=N-~N \$\endgroup\$ – Sp3000 Mar 2 '15 at 10:36
5
\$\begingroup\$

J, 19 characters, no bonus.

[:(/:+/"1@#:)@i.2^]
  • 2 ^ y – two to the power of y.
  • i. 2 ^ y – the integers from 0 to (2 ^ y) - 1.
  • #: i. 2 ^ y – each of these integers represented in base two.
  • +/"1 #: i. 2 ^ y – the sums of each representation
  • (i. 2 ^ y) /: +/"1 #: i. 2 ^ y – the vector i. 2 ^ y sorted by the order of the items of the previous vector, our answer.
\$\endgroup\$
3
\$\begingroup\$

Python, 63 chars

F=lambda n:`sorted(range(1<<n),key=lambda x:bin(x).count('1'))`

>>> F(3)
'[0, 1, 2, 4, 3, 5, 6, 7]'
\$\endgroup\$
  • \$\begingroup\$ @Alex: The list of restrictions implied he wanted a string result. \$\endgroup\$ – Keith Randall Mar 3 '15 at 0:30
  • \$\begingroup\$ Sorry, missed that. \$\endgroup\$ – Alex A. Mar 3 '15 at 1:43
3
\$\begingroup\$

C 179 * 0.5 = 89.5

main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(;n--;++i){for(o=0;o<m;++o){int bc=0,cb=28;for(;cb--;)bc+=o&(1<<cb)?1:0;if(bc==i)printf("%d ",o);}}printf("%d\n",m);return 0;}

EDIT: 157 * 0.5 = 78.5

main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(++n;n--;++i){for(o=0;o<=m;++o){int bc=0,cb=28;for(;cb--;)bc+=o&(1<<cb)?1:0;if(bc==i)printf("%d ",o);}}}

EDIT: 132 * 0.5 = 66

main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(++n;n--;++i){for(o=0;o<=m;++o){if(__builtin_popcount(o)==i)printf("%d ",o);}}}

or a bit nicer formatted:

main()
{
    int n, i = 0, m, o;
    scanf("%d", &n);
    m = ~((~0) << n);
    for(++n; n--; ++i)
    {
        for(o = 0; o <= m; ++o)
        {
            if (__builtin_popcount(o) == i)
                printf("%d ", o);
        }
    }
}

What it does?

m = ~((~0) << n);

calculates the last number to show (pow(2, n) - 1)

    for(++n; n--; ++i)
    {
        for(o = 0; o <= m; ++o)
        {

the outer loop iterates over the bit count (so 0 to n-1) while the inner loop just counts from 0 to m

            if (__builtin_popcount(o) == i)
                printf("%d ", o);

On x86 there is the POPCNT instruction that can be used to count the set bits. GCC and compatible compilers may support the __builtin_popcount function that basically compiles to that instruction.

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

CJam, 13 bytes

2ri#,{2b1b}$p

Pretty straight forward implementation.

How it works:

2ri#,             "Get an array of 0 to 2^n - 1 integers, where n is the input";
     {    }$      "Sort by";
      2b1b        "Convert the number to binary, sum the digits";
            p     "Print the array";

Try it online here

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

Mathematica, 50 46

SortBy[Range[0,2^#-1],Tr@IntegerDigits[#,2]&]&

.

SortBy[Range[0,2^#-1],Tr@IntegerDigits[#,2]&]&

{0, 1, 2, 4, 8, 16, 3, 5, 6, 9, 10, 12, 17, 18, 20, 
24, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 15, 
23, 27, 29, 30, 31}
\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner, Fixed! Thanks!!! \$\endgroup\$ – Savenkov Alexey Mar 1 '15 at 21:09
1
\$\begingroup\$

JavaScript (ES6) 41 (82*0.5)

The simplest way, golfed

F=b=>{
  for(l=0;l<=b;l++)
    for(i=1<<b;i;t||console.log(i))
      for(t=l,u=--i;u;--t)
        u&=u-1;
}

Ungolfed

F=b=>
{
  for (l = 0; l <= b; l++)
  {
    for (i = 1 << b; i > 0; )
    {
      --i;
      for (t = 0, u = i; u; ++t) // Counting bits set, Brian Kernighan's way
        u &= u - 1;
      if (t == l) console.log(i);
    }
  }
}

Test In Firefox/FireBug console

F(4)

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

\$\endgroup\$
1
\$\begingroup\$

Bash + coreutils, 66

One to get you started:

jot -w2o%dpc $[2**$1] 0|dc|tr -d 0|nl -ba -v0 -w9|sort -k2|cut -f1
\$\endgroup\$
  • \$\begingroup\$ Nothing really exciting here. Given your comment I will happily delete/revise this answer if you want to change the question. \$\endgroup\$ – Digital Trauma Feb 27 '15 at 5:46
  • \$\begingroup\$ Not sure if I should highlight your program must work for all values of n from 0 to 28 inclusive. I don't know how many answers here pass that requirement. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 27 '15 at 6:36
  • \$\begingroup\$ I have removed the clause, since people don't seem to notice it anyway. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 27 '15 at 10:37
  • \$\begingroup\$ @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Now, in theory at least it should work up to 28. I've tested up to 22 so far, but of course this makes sort take a long time. With n=28, sort will need to sort 2^28 lines / ~13GB of data. \$\endgroup\$ – Digital Trauma Feb 27 '15 at 20:32
1
\$\begingroup\$

Haskell, (87 * 0.5) = 43,5

f n=[0..n]>>=(\x->x#(n-x))
a#0=[2^a-1]
0#_=[0]
a#b=[1+2*x|x<-(a-1)#b]++[2*x|x<-a#(b-1)]

Usage example: f 4, which outputs [0,1,2,4,8,3,5,9,6,10,12,7,11,13,14,15]

How it works: neither sorting nor repeatedly iterating over [0..2^n-1] and looking for numbers containing i 1s.

The # helper functions takes two parameters a and b and constructs a list of every number made up of a 1s and b 0s. The main function f calls # for every combination of a and b where a+b equals n, starting with no 1s and n 0s to have the numbers in order. Thanks to Haskell's laziness all those lists don't have to be constructed completely in memory.

\$\endgroup\$
  • \$\begingroup\$ Doesn't the ++ in a#b mean that the left hand side (which could be large) needs to be produced entirely and then copied before the first item in the result is produced, thus violating the requirements for the bonus? \$\endgroup\$ – Jules Mar 31 '16 at 19:08
  • \$\begingroup\$ Ah, no, thinking about it can still lazily generate them while they're being produced, it just needs to make a copy of each item, which as both can be garbage collected during processing means that space usage is constant. Ignore me. \$\endgroup\$ – Jules Mar 31 '16 at 19:14
1
\$\begingroup\$

Ruby 47 chars

Much like the Python one from @KeithRandall :

f=->n{(0..1<<n).sort_by{|x|x.to_s(2).count ?1}}
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 26

Tr/@(2^Subsets@Range@#/2)&

Example:

Tr/@(2^Subsets@Range@#/2)&[4]

{0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12, 7, 11, 13, 14, 15}

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

Perl, 64/2 = 32

#!perl -ln
for$i(0..$_){$i-(sprintf"%b",$_)=~y/1//||print for 0..2**$_-1}

Simply iterate over the range [0..2^n-1] n + 1 times. In each iteration print only the numbers that have number of 1 bits equal to the iteration variable ($i). Bits are counted by counting 1's (y/1//) in the number converted to binary string with sprintf.

Test me.

Perl, 63

Sorting approach:

#!perl -l
print for sort{eval+(sprintf"%b-%b",$a,$b)=~y/0//dr}0..2**<>-1
\$\endgroup\$
  • 1
    \$\begingroup\$ @Optimizer, It uses O(1) memory. What other definition we have? Oops, that is not true as I print it live :) \$\endgroup\$ – nutki Feb 27 '15 at 8:49
  • \$\begingroup\$ @Optimizer, fixed. \$\endgroup\$ – nutki Feb 27 '15 at 9:02
  • \$\begingroup\$ Well, I am aware of this when I set the condition, but I allow it anyway, since I want to see what convoluted answers people can come up with. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 27 '15 at 9:44
  • 2
    \$\begingroup\$ I just asked "how" as I cannot read perl :) Care to add more explanation ? \$\endgroup\$ – Optimizer Feb 27 '15 at 9:48
  • \$\begingroup\$ @Optimizer, some more explanation added. \$\endgroup\$ – nutki Feb 27 '15 at 11:39
0
\$\begingroup\$

Java 8, 205

public class S{public static void main(String[] n){java.util.stream.IntStream.range(0,1<<Integer.parseInt(n[0])).boxed().sorted((a,b)->Integer.bitCount(a)-Integer.bitCount(b)).forEach(System.out::print);}}
\$\endgroup\$
0
\$\begingroup\$

C++11, 117 characters:

using namespace std;int main(){ set<pair<int,int> > s;int b;cin>>b;int i=0;while(++i<pow(2,b))s.insert({bitset<32>(i).count(),i});for (auto it:s) cout <<it.second<<endl;}

Ungolfed:

using namespace std;
int main()
{
    set<pair<int,int> > s;
    int b;
    cin>>b;
    int i=0;
    while (++i<pow(2,b))  {
        s.insert({bitset<32>(i).count(),i});
    }
    for (auto it:s) {
        cout <<it.second<<endl;
    }
}

Explanation:

Create a set of int,int pairs. The first int is bit count, the second one is the number. Pairs compare themselves according their first parameter, so the set is sorted by bit count.

\$\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.