All Binary Combinations to Decimal

Question

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

Answer 1

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 2^{x + y}, since the canonical binary representation of the latter has x + y + 1 digits.

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

Answer 2

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.

Answer 3

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]&

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.

Answer 13

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

Answer 14

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.

Answer 15

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]

Answer 16

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!

Answer 17

Japt, 10 bytes

ËçEìá mÍâ

Try it

ËçEìá mÍâ     :Implicit input of array
Ë              :Map each D at 0-based index E
 çE            :  Repeat E D times
   Ã           :End map
    ¬          :Join
     á         :Permutations
       m       :Map
        Í      :  Convert from binary string to integer
         â     :Deduplicate

Answer 18

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<...;)

Answer 19

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)