0
\$\begingroup\$

Challenge

Write the shortest program that receives two signed integers n and i and for each i between 1 and 2^n - 1 returns the next ordered permutation based on the binary representation of the number. There is no specific order of the combinations but the number of 1s in the binary representation must always stay the same or grow and numbers each output may happen only once

Clarification

The goal of this program is to generate all the combinations without repetitions of a set. To do so you may consider that each item is represented by a bit in a bit mask, that way if you have three items, A, B and C represented by 001, 010 and 100 respectively the combinations ABC, ACB, BCA, BAC, CAB and CBA are all represented as 111.

For increasing values of i your program should output a new combinations always with the same number of elements or more.

Input

You may read the input in the format

n i

or just use n and i variables, whichever suits you best.

Output

You may output a single number k

Sample cases

Each test case is two lines, input followed by output with a binary representation here for demonstration purposes:

3 1
1 (001)

3 2
4 (100)

3 3
2 (010)

3 4
6 (110)

3 7
7 (111)

Rules

  • Shortest code wins (bytes)
  • The result can be returned by a function or printed by your program.
  • You may assume n and i variables already exist, there's no need to handle input if you don't want to.
  • The answers with the same number of 1 bits can be output in any order
  • The input is guaranteed to be well formed and 1 <= i <= 2^n - 1.

Happy Golfing!

\$\endgroup\$

closed as unclear what you're asking by Peter Taylor, pawel.boczarski, Luis Mendo, Blue, ETHproductions Sep 12 '15 at 17:09

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ I don't get it. Can you explain a little more how you derive the output? \$\endgroup\$ – Luis Mendo Sep 11 '15 at 23:32
  • 3
    \$\begingroup\$ The first sentence is quite confusing, because you seem to be talking about two different is (one from input, and one which is a loop variable). On the third read-through of that sentence I came to the conclusion the "for each i" is actually intended to express a constraint on the possible inputs, and that seems to fit the rules at the end. But I'm still not sure what you mean by ordered permutation based on the binary representation of the number, and your example output doesn't seem to show a next-in-list function which the first sentence asks for. \$\endgroup\$ – Peter Taylor Sep 12 '15 at 8:08
  • \$\begingroup\$ I added a clarification, is it better to understand now? \$\endgroup\$ – fpg1503 Sep 12 '15 at 16:36
  • 1
    \$\begingroup\$ The example still seems to contradict the spec. Since the number of 1s must be non-decreasing, the next bitmask after 3 can't be 2. \$\endgroup\$ – Peter Taylor Sep 12 '15 at 20:19
1
\$\begingroup\$

Pyth, 13 bytes

i@o/N1^U2vzQ2

Just constructs a cartesian power of [0, 1], sorts it by number of 1s, and indexes before converting to base10.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 72 bytes

p [0,1].repeated_permutation(n).sort_by{|x|x.count 1}[i].join('').to_i 2

How it works:

irb(main):001:0> [0, 1].repeated_permutation(3).to_a  # generate permutations
=> [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1],
    [1, 1, 0], [1, 1, 1]]

irb(main):002:0> _.sort_by {|x| x.count 1 }           # sort by number of 1's
=> [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [0, 1, 1], [1, 0, 1],
    [1, 1, 0], [1, 1, 1]]

irb(main):003:0> _[2].join ''  # convert array of binary digits to string
=> "010"
irb(main):004:0> _.to_i 2      # interpret string as binary number
=> 2
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.