3

I'm new to Stackexchange and maybe I do not have the correct mathematical terms for the question I'm about to ask.

I'm given a multiset of given size $N$ which consists of zeros and ones.

Example:

Multiset size $5$ with number of ones: $2$, number of zeros: $3$

How many distinct arrangements (sequences) of all these items are possible?

First arrangement is: $0,0,0,1,1$

Listing all arrangements in ascending order:

1: $0,0,0,1,1$

2: $0,0,1,0,1$

3: $0,0,1,1,0$

4: $0,1,0,0,1$

5: $0,1,0,1,0$

6: $0,1,1,0,0$

7: $1,0,0,0,1$

8: $1,0,0,1,0$

9: $1,0,1,0,0$

10: $1,1,0,0,0$

Because in a real task the set size could be much larger than this example, is it possible without iterating through all arrangements:

  1. To find the $n^{\text{th}}$ arrangment in the lexicographically ordered list (example $7^{\text{th}}$ permutation = $1,0,0,0,1$) ?

  2. To calculate the index if I'm given the arrangement (example $0,1,0,1,0 = 5$) ?

I'm looking for an algorithm suitable for implementation in some programming language.

hardmath
  • 37,015
Duje Lalic
  • 33
  • I hope it's not for an assignment or a contest problem. – user21820 Aug 12 '15 at 10:03
  • 1
    When a collection contains repetitions of an item, we call it a multiset (or sometimes a bag) rather than a set. This is because the items that belong to a set are necessarily distinct. – hardmath Aug 12 '15 at 14:04
  • @joriki: This problem involves repetitions. The equivalence (when only two distinct kinds of items are present) to choosing combinations (subsets) of distinct items may not be entirely obvious. – hardmath Aug 12 '15 at 14:21
  • @hardmath: I would have thought that the analogy between distributing x's and distributing $1$'s would be clear enough, but if it isn't, it can be pointed out (as you have) in a comment -- in any case it should be treated as a duplicate and not answered separately. – joriki Aug 12 '15 at 15:37
  • 2
    Guys I just got to the computer! I'm overwhelmed with the answers! By a quick glance I believe it is a duplicate! I will check now... @hardmath, you guessed right I'm not comfortable with the terminology and that was why I had the problem finding the right answer just by using Google. All that was written here, all the comments, helped me greatly!! I'm very thankful! Regarding the real task... It's just a method of optimally saving lots of on/off flags from one experiment. So it is just 0 and 1 ... and the size could be around 500 flags ... where most are zero and some are 1... – Duje Lalic Aug 12 '15 at 17:36
  • 1
    @hardmath: I must admit I've grown increasingly sceptical about guessing what else a question may have been intended to refer to. Protracted discussions that elucidate a different intended question tend to result in long comment threads and invalidated answers to the original question. I think questions should be taken at face value the way they are posed, by all means clarified, but not changed, and if a different question turns out to have been intended, a new question should be asked. Closing a question doesn't prevent the OP from doing that. – joriki Aug 12 '15 at 17:45

1 Answers1

1

If you have $N$ elements and $k$ of them are $1$'s, there are $N \choose k$ total arrangements. The first element will be a $1$ in the last ${N-1 \choose k-1}$ of them, so if your position in the list is less than that, the first element is a zero. Otherwise it is a $1$. This should suggest a recursive algorithm.

Going the other way works the same. If the first element is $1$, it comes after all the ${N-1 \choose k}$ items that start with $0$. If the first element is $0$, it doesn't force the arrangement to come after any others. Add up the number of arrangements the $1$'s force you to be after. Again, this is a nice recursive algorithm.

It is a bit easier if you start counting the arrangements from $0$, not $1$.

Ross Millikan
  • 374,822