0
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
andi
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!
4I don't get it. Can you explain a little more how you derive the output? – Luis Mendo – 2015-09-11T23:32:19.057
3The first sentence is quite confusing, because you seem to be talking about two different
i
s (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 eachi
" 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. – Peter Taylor – 2015-09-12T08:08:03.880I added a clarification, is it better to understand now? – fpg1503 – 2015-09-12T16:36:18.993
1The example still seems to contradict the spec. Since the number of 1s must be non-decreasing, the next bitmask after
3
can't be2
. – Peter Taylor – 2015-09-12T20:19:43.413