12
\$\begingroup\$

Disclaimer

This question is not a duplicate of this question. I'm not counting specific digits, as we already have those set in the initial parameters. This question is focusing on the decimal numbers that can be constructed from the binary strings based on the digits provided.

Challenge

Given two integers X and Y, representing the number of zeroes (0) and ones (1) respectively, calculate all the possible decimal equivalents that can be determined from creating binary strings using only the zeroes and ones provided, and display them as output.

Example 1:

Input: 0 1

Output: 1

Explanation: Only one 1 to account for, which can only be converted one way.

Example 2:

Input: 1 1

Output: 1,2

Explanation: 01 converts to 1, 10 converts to 2.

Example 3:

Input: 3 2

Output: 3,5,6,9,10,12,17,18,20,24

Explanation: Three 0s and two 1s make 00011 (3), 00101 (5), 00110 (6), 01001 (9), 01010 (10), 01100 (12), 10001 (17), 10010 (18), 10100 (20), 11000 (24)

Limitations and Rules

  • I will only expect your code to work where 0 < X + Y <= 16 so the maximum number in the output could only occur from 16 1s, i.e. parameters 0 and 16.
  • As a result of the above limitation, the range of numbers we'd expect in the output are from 0 and 65535.
  • I will accept functions or code, so long as the resulting output is provided, whether this be a comma separated list, an array, list outputted to STDOUT, etc. The only criteria I must stress about the output is that it must be sorted.
  • This is code golf, minimum bytes will receive maximum glory.
  • We will not tolerate silly loopholes
\$\endgroup\$
  • 1
    \$\begingroup\$ Does the output have to be sorted? \$\endgroup\$ – Dennis Sep 7 '16 at 1:47
  • \$\begingroup\$ Hi @Dennis, yes, I forgot to mention that... the output must be sorted. I've updated the rules accordingly. \$\endgroup\$ – WallyWest Sep 7 '16 at 1:49
  • 2
    \$\begingroup\$ Do we need to handle case 0 0? \$\endgroup\$ – ETHproductions Sep 7 '16 at 1:55
  • \$\begingroup\$ @ETHproductions I mentioned above that 0 <= X + Y <= 16, so yes, because 0 0 would be considered valid input that satisfies that rule. \$\endgroup\$ – WallyWest Sep 7 '16 at 2:05
  • 2
    \$\begingroup\$ In that case, what's the expected output for 0 0? The number 0 can be represented by zero, one or more zeroes. \$\endgroup\$ – Dennis Sep 7 '16 at 2:09

18 Answers 18

5
\$\begingroup\$

Jelly, 8 bytes

0,1xŒ!ḄQ

Try it online!

How it works

0,1xŒ!ḄQ Main link. Argument: [x, y]

0,1x     Repeat 0 x times and 1 y times.
    Œ!   Compute all permutations of the result.
      Ḅ   Unbinary; convert each permutation from base 2 to integer.
       Q  Unique; deduplicate the results.
\$\endgroup\$
  • \$\begingroup\$ This is quite impressive... Is there much call for J in the general programming market? I noticed Jelly is based off it? \$\endgroup\$ – WallyWest Sep 7 '16 at 1:53
  • 1
    \$\begingroup\$ It has a user base in some specific applications (mostly math/statistics), but I honestly don't know. I haven't used J outside of code golf. \$\endgroup\$ – Dennis Sep 7 '16 at 1:58
  • \$\begingroup\$ @WallyWest It isn't called for often because it is best suited for an environment that would benefit from functional programming. Usually only for very specialized programming. \$\endgroup\$ – Conor O'Brien Sep 8 '16 at 3:29
7
\$\begingroup\$

Python, 60 bytes

lambda x,y:[n for n in range(1<<x+y)if bin(n).count('1')==y]

Test it on Ideone.

How it works

All positive numbers that can be represented in binary with x zeroes and y ones is clearly smaller than 2x + y, since the canonical binary representation of the latter has x + y + 1 digits.

The lambda simply iterates over the integers in [0, 2x + y) and keeps all integers n in that range that have y ones. Since n < 2x + y is can be represented with x (or less) zeroes.

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

Mathematica, 59 57 bytes

A usual outcome with Mathematica: high-level functions = good, long function names = bad.

#+##&~Fold~#&/@Permutations@Join[0&~Array~#,1&~Array~#2]&

Join[0&~Array~#,1&~Array~#2] creates a list with the correct number of 0s and 1s. Permutations generates all permutations of that list, without repetitions (as I learned) and in sorted order. #+##&~Fold~# (a golfuscated version of #~FromDigits~2) converts a list of base-2 digits into the integer they represent.

Previous version, before Martin Ender's comment:

#~FromDigits~2&/@Permutations@Join[0&~Array~#,1&~Array~#2]&
\$\endgroup\$
  • 1
    \$\begingroup\$ Nevertheless, well observed and documented... Mathematica is great for number crunching, not as good for code golf... well, some of the time... \$\endgroup\$ – WallyWest Sep 7 '16 at 6:52
  • 1
    \$\begingroup\$ FromDigits can usually be shortened: #+##&~Fold~#&/@Permutations... \$\endgroup\$ – Martin Ender Sep 7 '16 at 8:03
  • \$\begingroup\$ @MartinEnder: I get it! and see how to generalize to other bases as well. Thank you for teaching me this clever idiom. \$\endgroup\$ – Greg Martin Sep 7 '16 at 8:12
  • 1
    \$\begingroup\$ Credits for coming up with it go to alephalpha. ;) \$\endgroup\$ – Martin Ender Sep 7 '16 at 8:13
  • 1
    \$\begingroup\$ It turns out that switching to Dennis's approach is shorter though: Select[Range[2^+##]-1,x=#;DigitCount[#,2,1]==x&]& \$\endgroup\$ – Martin Ender Sep 7 '16 at 8:16
5
\$\begingroup\$

CJam (15 14 bytes)

{As.*s:~e!2fb}

This is an anonymous block (function) which takes input as an array [number-of-ones number-of-zeros] and returns output as an array.

Online demo


A long way off the mark, but more interesting: this is without permutation builtins or base conversion:

{2\f#~1$*:X;[({___~)&_2$+@1$^4/@/|_X<}g;]}

It would work nicely as a GolfScript unfold.

\$\endgroup\$
  • \$\begingroup\$ I was trying to replace the ee{)*}/ with something using .* and came up with this 14-byte solution: {As.*s:~e!2fb} The s:~ looks a bit inefficient now though. \$\endgroup\$ – Martin Ender Sep 7 '16 at 8:09
  • 1
    \$\begingroup\$ @MartinEnder, I actually started with .* and decided that ee was nicer than e.g. 2,:a.*e_. I didn't realise though that e! will give the same output regardless of the order of its argument. \$\endgroup\$ – Peter Taylor Sep 7 '16 at 8:34
  • \$\begingroup\$ Yeah, I only discovered this the other day myself. \$\endgroup\$ – Martin Ender Sep 7 '16 at 8:35
4
\$\begingroup\$

Japt, 16 bytes

'0pU +'1pV)á mn2

Test it online!

How it works

                  // Implicit: U = first integer, V = second integer
'0pU              // Repeat the string "0" U times.
     +'1pV)       // Concatenate with the string "1" repeated V times.
           á      // Take all unique permutations.
             mn2  // Interpret each item in the resulting array as a binary number.
                  // Implicit: output last expression

Alternate version, 17 bytes

2pU+V o f_¤è'1 ¥V
                   // Implicit: U = first integer, V = second integer
2pU+V              // Take 2 to the power of U + V.
      o            // Create the range [0, 2^(U+V)).
        f_         // Filter to only items where
           è'1     //  the number of "1"s in
          ¤        //  its binary representation
               ¥V  //  is equal to V. 
                   // Implicit: output last expression

I've been trying to further golf both versions, but I just can't find any slack...

\$\endgroup\$
  • \$\begingroup\$ This looks amazing... and it works great! The interpreter isn't showing the transpiled code on the right, however? I'd love to see how it renders? \$\endgroup\$ – WallyWest Sep 7 '16 at 1:38
  • \$\begingroup\$ @WallyWest It transpiles roughly to ("0".p(U)+"1".p(V)).á().m("n",2); each of the .x() functions is defined in the source file. \$\endgroup\$ – ETHproductions Sep 7 '16 at 1:41
3
\$\begingroup\$

Ruby, 63 bytes

A simple implementation. Golfing suggestions welcome.

->a,b{(?0*a+?1*b).chars.permutation.map{|b|(b*'').to_i 2}.uniq}

Ungolfing

def f(a,b)
  str = "0"*a+"1"*b                   # make the string of 0s and 1s
  all_perms = str.chars.permutation   # generate all permutations of the 0s and 1s
  result = []
  all_perms.do each |bin|             # map over all of the permutations
    bin = bin * ''                    # join bin together
    result << bin.to_i(2)             # convert to decimal and append
  end
  return result.uniq                  # uniquify the result and return
end
\$\endgroup\$
3
\$\begingroup\$

Pyth - 11 bytes

{iR2.psmVU2

Test Suite.

{                Uniquify
 iR2             Map i2, which converts from binary to decimal
  .p             All permutations
   s             Concatenate list
    mV           Vectorized map, which in this case is repeat
     U2          0, 1
     (Q)         Implicit input
\$\endgroup\$
2
\$\begingroup\$

Python 2 - 105 99 bytes

+8 bytes cos our output needs to be sorted

lambda x,y:sorted(set(int("".join(z),2)for z in __import__('itertools').permutations("0"*x+"1"*y)))
\$\endgroup\$
  • \$\begingroup\$ Impressive edit! \$\endgroup\$ – WallyWest Sep 7 '16 at 1:54
  • 1
    \$\begingroup\$ Thanks, I had no idea you could import modules in lambda functions. \$\endgroup\$ – Jeremy Sep 7 '16 at 1:56
  • \$\begingroup\$ I always thought you were allowed to have a separate import statement for the purposes of code golf. (Obviously you still need to include its length.) This might save you a byte or two? \$\endgroup\$ – Neil Sep 7 '16 at 8:37
2
\$\begingroup\$

Mathematica, 47 bytes

Cases[Range[2^+##]-1,x_/;DigitCount[x,2,1]==#]&

An unnamed function taking two arguments: number of 1s, number of 0s.

Essentially a port of Dennis's Python solution. We create a range from 0 to 2x+y-1 and then keep only those numbers whose amount of 1-bits equals the first input. The most interesting bit is probably the 2^+## which uses some sequence magic to avoid the parentheses around the addition of the two arguments.

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

MATLAB 57 + 6

@(a,b)unique(perms([ones(1,a) zeros(1,b)])*2.^(0:a+b-1)')

run using

ans(2,3)

ungolfed

function decimalPerms( nZeros, nOnes )
  a = [ones(1,nOnes) zeros(1,nZeros)];  % make 1 by n array of ones and zeros
  a = perms(a);                         % get permutations of the above 
  powOfTwo = 2.^(0:nOnes+nZeros-1)';    % powers of two as vector
  a = a * powOfTwo;                     % matrix multiply to get the possible values
  a = unique(a)                         % select the unique values and print
\$\endgroup\$
  • 1
    \$\begingroup\$ What's the plus 6 bytes for? \$\endgroup\$ – mbomb007 Sep 7 '16 at 13:44
  • \$\begingroup\$ I was about to ask the same thing \$\endgroup\$ – WallyWest Sep 7 '16 at 14:15
2
\$\begingroup\$

MATL, 9 bytes

y+:<Y@XBu

Try it online!

Explanation

The approach is similar to that in Dennis' Jelly answer.

y     % Implicitly take two inputs (say 3, 2). Duplicate the first.
      %   STACK: 3, 2, 3
+     % Add
      %   STACK: 3, 5
:     % Range
      %   STACK: 3, [1 2 3 4 5]
<     % Less  than
      %   STACK: [0 0 0 1 1]
Y@    % All permutations
      %   STACK: [0 0 0 1 1; 0 0 0 1 1; ...; 0 0 1 0 1; ...; 1 1 0 0 0]
XB    % Binary to decimal
      %   STACK: [3 3 ... 5 ... 24]
u     % Unique
      %   STACK: [3 5 ... 24]
      % Implicitly display
\$\endgroup\$
1
\$\begingroup\$

Actually, 21 bytes

A port of my Ruby answer. Golfing suggestions welcome. Try it online!

│+)'1*@'0*+╨`εj2@¿`M╔

How it works

          Implicit input of a and b.
│+)       Duplicate a and b, add, and rotate to bottom of stack. Stack: [b a a+b]
'1*@      "1" times b and swap with a.
'0*+      "0" times a and add to get "0"*a+"1"*b.
╨`...`M   Take all the (a+b)-length permutations of "0"*a+"1"*b
          and map the following function over them.
  εj        Join the permutation into one string
  2@¿       Convert from binary to decimal
╔         Uniquify the resulting list and implicit return.
\$\endgroup\$
1
\$\begingroup\$

Groovy 74 Bytes, 93 Bytes or 123 Bytes

I don't know which one you consider more fully answers the question but...

74 Byte Solution

​{a,b->((1..a).collect{0}+(1..b).collect{1}).permutations().unique()}(1,2)

For an input of 1,2 you get:

[[1,0,1], [0,1,1], [1,1,0]]

93 Byte Solution

{a,b->((1..a).collect{0}+(1..b).collect{1}).permutations().collect{it.join()}.unique()}(1,2)​

For an input of 1,2 you get:

[101, 011, 110]

123 Byte Solution

{a,b->((1..a).collect{0}+(1..b).collect{1}).permutations().collect{it.join()}.unique().collect{Integer.parseInt(it,2)}}(1,2)

For an input of 1,2 you get:

[5, 3, 6]

Try it out here:

https://groovyconsole.appspot.com/edit/5143619413475328

\$\endgroup\$
  • \$\begingroup\$ I'd be counting the 123 byte solution as this matches the output type mentioned in the brief. Well done. \$\endgroup\$ – WallyWest Sep 7 '16 at 19:34
1
\$\begingroup\$

JavaScript (Firefox 48), 85 76 74 71 70 bytes

Saved 3 bytes thanks to @Neil.

(m,n,g=x=>x?g(x>>1)-x%2:n)=>[for(i of Array(1<<m+n).keys())if(!g(i))i]

Array comprehensions are awesome. Too bad they haven't made it into official ECMAScript spec yet.

JavaScript (ES6), 109 87 79 78 71 70 bytes

(m,n,g=x=>x?g(x>>1)-x%2:n)=>[...Array(1<<m+n).keys()].filter(x=>!g(x))

Should work in all ES6-compliant browsers now. Saved 7 bytes on this one, also thanks to @Neil.

\$\endgroup\$
  • \$\begingroup\$ Uh, @ETHProductions, for some reason I'm getting it returning undefined now with every test run I'm doing...? \$\endgroup\$ – WallyWest Sep 7 '16 at 2:14
  • \$\begingroup\$ @WallyWest Make sure you're first assigning it to a variable, e.g. f=(m,n)=>..., then call it like f(3,2). If that's what you're doing, what browser are you using? \$\endgroup\$ – ETHproductions Sep 7 '16 at 2:15
  • \$\begingroup\$ Chrome 52... I don't have firefox on this machine, so I could only test the ES6 non-Firefox version... \$\endgroup\$ – WallyWest Sep 7 '16 at 2:17
  • \$\begingroup\$ Trying to run it inthe browser console. \$\endgroup\$ – WallyWest Sep 7 '16 at 2:17
  • \$\begingroup\$ Oh, hmm. I see that problem too in Chrome. Try this eval-less version (does exactly the same thing, but 3 bytes longer): (m,n)=>{a="";for(i=0;i<1<<m+n;i++)if(i.toString(2).split(1).length==n+1)a+=i+" ";return a} \$\endgroup\$ – ETHproductions Sep 7 '16 at 2:20
1
\$\begingroup\$

Groovy 80 Bytes

based on the answer by @carusocomputing

his 123 Byte solution can be compressed into 80 Bytes:

80 Byte Solution

{a,b->([0]*a+[1]*b).permutations()*.join().collect{Integer.parseInt(it,2)}}(1,2)

For an input of 1,2 you get:

[5, 3, 6]
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 72 68 bytes

f(a,b){for(a=1<<a+b;a--;)__builtin_popcount(a)^b||printf("%d\n",a);}

Try it online!

Unfortunately there is no popcount() in the standard library, but it is provided as a "builtin function" by GCC. The output is sorted, but in reverse order.

Thanks to @ceilingcat for shaving off 4 bytes!

\$\endgroup\$
  • \$\begingroup\$ Still acceptable. Nice work! \$\endgroup\$ – WallyWest Sep 8 '16 at 10:51
0
\$\begingroup\$

PHP, 80 or 63 bytes

depending on wether I must use $argv or can use $x and $y instead.

for($i=1<<array_sum($argv);$i--;)echo$argv[2]-substr_count(decbin($i),1)?_:$i._;

prints all matching numbers in descending order delimited by underscores.
filename must not begin with a digit.

no builtins, 88 or 71 bytes

for($i=1<<array_sum($argv);$i--;print$c?_:$i._)for($n=$i,$c=$argv[2];$n;$n>>=1)$c-=$n&1;

add one byte each for only one underscore after every number.

@WallyWest: You were right. Saves 3 bytes for me from for($i=-1;++$i<...;)

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

Perl 6,  64 62  49 bytes

{(0 x$^a~1 x$^b).comb.permutations.map({:2(.join)}).sort.squish}
{[~](0,1 Zx@_).comb.permutations.map({:2(.join)}).sort.squish}
{(^2**($^x+$^y)).grep:{.base(2).comb('1')==$y}}

Explanation:

# bare block lambda with two placeholder parameters 「$^x」 and 「$^y」
{
  # Range of possible values
  # from 0 up to and excluding 2 to the power of $x+$y
  ( ^ 2 ** ( $^x + $^y ) )

  # find only those which
  .grep:

  # bare block lambda with implicit parameter of 「$_」
  {

    # convert to base 2
    # ( implicit method call on 「$_」 )
    .base(2)

    # get a list of 1s
    .comb('1')

    # is the number of elements the same
    ==

    # as the second argument to the outer block
    $y
  }
}
say {(0..2**($^x+$^y)).grep:{.base(2).comb('1')==$y}}(3,2)
# (3 5 6 9 10 12 17 18 20 24)
\$\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.