Duplicate selection algorithm Selection (counting method)
Source: http: //blog.9cbs.net/cxjddd/archive/2004/07/29/55752.aspx
Sorry, I can't use an accurate title, the following description: There is a certain number of elements (assuming no duplicate), copying an element each time; listing all possible results when copying several times. For example, copy 2 times from {1, 2, 3}, can be (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) A total of six.
Each group of results can be expressed in the number of each element, as in front (1, 1), one of which has 2, the other two elements are not, can be expressed as [2, 0, 0]; (2, 3) can be expressed as [0, 1, 1]; the same, [0, 0, 2] can be represented (3, 3). This method represented by the number of each element can be referred to as a "count method".
If the result is arranged in a word ordered, the arranging of the counting method of the previous example is:
[2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2].
It can be seen that the starting state of the counting method is simple, that is, the end state is also simple, that is, [0, 0, ..., 0, n]. As long as the former can turn the former, it is equivalent to completing all arrangements.
Obviously, the next result of [N, 0, 0, ..., 0] will be [N-1, 1, 0, ..., 0]; if we put the back [1, 0, ... 0] It is clear that it is "new" count, it is obvious to change into [0, 1, ..., 0], so that it can always change to [0, 0, ..., 1]; [N, 0, 0, ..., 0] varies to [N-1, 0, 0, ..., 1].
What will the next one of [N-1, 0, 0, ..., 1]? It can be affirmed, it is [N-2, 2, 0, ..., 0]. Because the next result of (1, 3) is (2, 2), this is the smallest change. This is equivalent to borrowing a "high". Similarly, we can use "recursive" approach to changing [2, 0, ..., 0] to [0, 0, ..., 2]. So now it has become [N-2, 0, 0, ..., 2].
([2, 0, ..., 0] can become [1, 1, ..., 0], then [1, 0, ..., 1], change [0, 2,. .., 0]. Recursive. In the end, there will be [2, 0], naturally it can become [1, 1], and then "borrow" to become [0, 2])
Similarly, [N-2, 0, 0, ..., 2] can become [N-3, 3, 0, ..., 0]; then become [N-3, 0, 0,. .., 3]. From this, it can vary to [1, 0, 0, ..., N-1]. At this time, it will become [0, n, 0, ..., 0], to this first element, complete all the results. Of course, a new [n, 0, ..., 0] appeared, can also be completed.
Special, there will be [N, 0], this is from [N-1, 1], [N-2, 2], etc., until [1, N-1], [0, N] is completed.
Summarize the above situation:
[N, 0, 0, ..., 0, 0] [N-1, 1, 0, ..., 0, 0] [N-1, 0, 1, ..., 0, 0]. .. [N-1, 0, 0, ..., 0, 1] [N-2, 2, 0, ..., 0, 0] [N-2, 1, 1, ..., 0 0] ... [N-2, 1, 0, ..., 0, 1] [N-2, 0, 2, ..., 0, 0] ... [N-2, 0, 0, ..., 2, 0] [N-2, 0, 0, ..., 1, 1] [N-2, 0, 0, ..., 0, 2] [N-3, 3 , 0, ..., 0, 0] ... [1, N-1, 0, ..., 0, 0] ... [1, 0, 0, ..., 0, n-1 ] [0, N, 0, ..., 0, 0] ... [0, 0, 0, ..., N, 0] [0, 0, 0, ..., N-1, 1 ] [0, 0, 0, ..., N-2, 2] ... [0, 0, 0, ..., 1, n-1] [0, 0, 0, ..., 0 , n] Summary of the above case: starting from the top right,
First, for [N, 0, ..., 0], become [N-1, 1, ..., 0];
Second, for [N, 0, ..., M], becomes [N-1, M 1, ..., 0].
(Note: [N, M] (M and N is greater than 0) According to "Situation 2"
In the process of writing the program, it can be deformed above, divided into [N, 0, ..., 0, M] and [N, M], where n> 0, m> = 0. The foregoing became [N-1, M 1, ..., 0, 0]; and the latter becomes [N-1, M 1].
The procedure is as follows:
Template
Bool
Next_selection (Biiter First, Biiter Last)
{
IF (first == last)
Return False;
Biiter I = Last;
IF (--i == first)
Return False;
Biiter J = I;
IF (* - i == 0)
{
While ((i! = first) && (* i == 0))))
i;
IF (* i == 0)
{
Iter_Swap (First, J);
Return False;
}
Biiter II = i;
* ( ii) = * j 1;
* j = 0;
- * i;
}
Else
{
- * i;
* j;
}
Return True;
}
The front is next_selection, a word; and prev_selection (equivalent to reverse word order) can also be achieved more simply.
Observing that [M, N] (where n> 0) is turned [M 1, N-1]; [M, N, 0, ..., 0] (where n> 0), change [M 1, 0, 0, ..., N-1]. The procedure is as follows:
Template
Bool
Prev_Selection (Biiter First, Biiter Last)
{
IF (first == last)
Return False;
Biiter I = Last;
i;
IF (first == i) Return False;
IF (* i == 0)
{
While (* - i == 0)
;
IF (i == first)
{
* - last = * i;
* i = 0;
Return False;
}
Biiter J = I;
--j;
* j;
- * i;
iter_swap (i, --last);
}
Else
{
Biiter J = I;
--j;
* j;
- * i;
}
Return True;
}
