在一个有序集合，计算一个定数的指数 [英] Calculate the index of a given number within a sorted set

问题描述

不知道这个问题应该在数学，溢出或在这里，所以会尽量在这里第一次：

Not sure if this question should be on Math-Overflow or here, so will try here first:

假设我们给出了一些有N 1S和M 0。

Suppose we are given a number with N 1s and M 0s.

有（M + N）！/（M！* N！）不同这样的数字，可以在一个可数集进行排序。

There are (M+N)!/(M!*N!) different such numbers, that can be sorted in a countable set.

例如，有序集合有2个1和3个零的所有数字，是：

For example, the sorted set of all numbers with 2 ones and 3 zeros, is:

• 0 00011
• 1 00101
• 2 00110
• 3 01001
• 4 01010
• 5 01100
• 6 10001
• 7 10010
• 8 10100
• 9 11000

• 0 00011
• 1 00101
• 2 00110
• 3 01001
• 4 01010
• 5 01100
• 6 10001
• 7 10010
• 8 10100
• 9 11000

如何才能有效地计算相应的一组中的给定数量的指数？

How can we efficiently calculate the index of a given number within the corresponding set?

注：输入到这个问题的仅的数量，和不可以整（相应的）集

Note: the input to this question is only the number, and not the entire (corresponding) set.

推荐答案

让选择（N，K）= N！ / K！ /（N-K）！。

观察你的有序集合的结构如下：

Observe the following structure of your sorted set:

    0 0 | 0011     1 0 | 0101     2 0 | 0110     3 0 | 1001     4 0 | 1010     5 0 | 1100       ------     6 1 | 0001     7 1 | 0010     8 1 | 0100     9 1 | 1000

0 0|0011 1 0|0101 2 0|0110 3 0|1001 4 0|1010 5 0|1100 ------ 6 1|0001 7 1|0010 8 1|0100 9 1|1000

在有序集合，有选择（N + M，M）号（长二进制字符串 N + M ）的总和。 首先去开始一个零的数字，并有选择（N + M-1，M-1）他们。然后去开始由一个个的数字，并有选择（N-1 + M，M）他们。每个这两部分的还排序

In the sorted set, there are choose (N + M, M) numbers (binary strings of length N + M) in total. First go the numbers starting by a zero, and there are choose (N + M-1, M-1) of them. Then go the numbers starting by a one, and there are choose (N-1 + M, M) of them. Each of these two sections is also sorted.

所以，如果你的号码B ₁ B ₂ 。B <子> K 以一个零（B _{1 = 0），其在有序集合指数是一样的B指数 2 。B <子> K} 的有序集合的所有二进制串<$ C $ç> N 1和 M-1 零。如果用一个（B ₁ = 1），其在有序集合指数是一样的B指数 ₂ 。B <子> K <启动/ SUB>的有序集合的所有二进制字符串 N-1 1和 M 零，加的二进制字符串的总人数开始以零，这是选择（N + M-1，M-1）。

So, if your number b₁b₂...b_k starts with a zero (b₁ = 0), its index in the sorted set is the same as index of b₂...b_k in the sorted set of all binary strings of N ones and M-1 zeroes. If it starts with a one (b₁ = 1), its index in the sorted set is the same as index of b₂...b_k in the sorted set of all binary strings of N-1 ones and M zeroes, plus the total number of binary strings starting with a zero, which is choose (N + M-1, M-1).

在这种方式，你递归下降到涉及您的原始二进制字符串的后缀子问题，增加了寻求数量一定量每当你遇到一个1到最后，你来一个空的二进制字符串这显然是独一无二的由0零和0那些只有字符串。

In this way, you recursively descent to subproblems involving suffixes of your original binary string, increasing the sought number by some amount whenever you meet a 1. In the end, you come to an empty binary string which clearly is the one and only string consisting of 0 zeroes and 0 ones.

这篇关于在一个有序集合，计算一个定数的指数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！