|
numeric
|
Twiddle algorithm – modifications applied only to simplify integration. More...
#include <Twiddle.hpp>
Public Member Functions | |
| Twiddle () | |
| ~Twiddle () | |
| bool | next () |
| bool | isActivePosition (size_t position) const |
| void | init (int m, int n) |
Twiddle algorithm – modifications applied only to simplify integration.
The implementation uses: twiddle.c – retrieved from http://www.netlib.no/netlib/toms/382
Twiddle generates all combinations of M elements drawn without replacement from a set of N elements. This routine may be used in two ways: (0) To generate all combinations of M out of N objects, let a[0..N-1] contain the objects, and let c[0..M-1] initially be the combination a[N-M..N-1]. While twiddle(&x, &y, &z, p) is false, set c[z] = a[x] to produce a new combination. (1) To generate all sequences of 0's and 1's containing M 1's, let b[0..N-M-1] = 0 and b[N-M..N-1] = 1. While twiddle(&x, &y, &z, p) is false, set b[x] = 1 and b[y] = 0 to produce a new sequence. In either of these cases, the array p[0..N+1] should be initialised as follows: p[0] = N+1 p[1..N-M] = 0 p[N-M+1..N] = 1..M p[N+1] = -2 if M=0 then p[1] = 1 In this implementation, this initialisation is accomplished by calling inittwiddle(M, N, p), where p points to an array of N+2 ints.
Coded by Matthew Belmonte mkb4@Cornell.edu, 23 March 1996 Copyright (c) 1996 by Matthew Belmonte. Permission for use and distribution is hereby granted, subject to the restrictions that this copyright notice and reference list be included in its entirety, and that any and all changes made to the program be clearly noted in the program text.
This software is provided 'as is', with no warranty, express or implied, including but not limited to warranties of merchantability or fitness for a particular purpose. The user of this software assumes liability for any and all damages, whether direct or consequential, arising from its use. The author of this implementation will not be liable for any such damages.
Reference:
Phillip J Chase, `Algorithm 382: Combinations of M out of N Objects [G6]', Communications of the Association for Computing Machinery 13:6:368 (1970). The returned indices x, y, and z in this implementation are decremented by 1, in order to conform to the C language array reference convention. Also, the parameter 'done' has been replaced with a Boolean return value.
Here is a sample using the original of twiddle:
#define N 5
#define M 2
#include <stdio.h>
void main()
{
int i, x, y, z, p[N+2], b[N];
inittwiddle(M, N, p);
for(i = 0; i != N-M; i++)
{
b[i] = 0;
putchar('0');
}
while(i != N)
{
b[i++] = 1;
putchar('1');
}
putchar('\n');
while(!twiddle(&x, &y, &z, p))
{
b[x] = 1;
b[y] = 0;
for(i = 0; i != N; i++)
putchar(b[i]? '1': '0');
putchar('\n');
}
}Current interface has been simplified to the following:
Twiddle twiddle;
twiddle.init(2,5);
while(twiddle.next())
{
// Construct the final combination from
// the active positions, e.g. by mapping
// to position of an itemlist
for(size_t pos = 0; pos < 5; ++pos)
{
if(twiddle.isActivePosition(pos))
{
...
}
}
}
| numeric::Twiddle::Twiddle | ( | ) |
Default contructor
| numeric::Twiddle::~Twiddle | ( | ) |
Default destructor
| void numeric::Twiddle::init | ( | int | m, |
| int | n | ||
| ) |
Initialize the algorithm
| m | Number of objects that shall be combined |
| n | Total number of objects |
| bool numeric::Twiddle::isActivePosition | ( | size_t | position | ) | const |
Check if the current position is active, i.e. belongs to the current combination
| bool numeric::Twiddle::next | ( | ) |
Run the twiddle algorithm
1.8.13