test/utils/GenerateCombination.hpp

/*
 * Copyright (C) 2000-2004  Object Oriented Parallel Simulation Engine (OOPSE) project
 * 
 * Contact: oopse@oopse.org
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1
 * of the License, or (at your option) any later version.
 * All we ask is that proper credit is given for our work, which includes
 * - but is not limited to - adding the above copyright notice to the beginning
 * of your source code files, and to any copyright notice that you may distribute
 * with programs based on this work.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

/**
 * @file GenerateCombination.hpp
 * @author    tlin
 * @date  10/27/2004
 * @version 1.0
 */ 

#ifndef UTILS_GENERATECOMBINATION_HPP
#define UTILS_GENERATECOMBINATION_HPP

#include <vector>

namespace oopse {
//this algorithm can be modified to be compatible with STL container
//Basically, changes totNum to last iteratir and beginIndex to first iterator, sequence from
//a vector<int> to a vector<iterator>, STL compatible version will be committed next time
bool next_combination(std::vector<int> sequence, int totNum, int beginIndex = 0) {
    int endIndex = beginIndex + totNum - 1;
    int currentSize;
    currentSize = sequence.size();
    
    if (currentSize == 0) {
        //if sequence is empty, we push the begin index into it
        sequence.push_back(beginIndex);
        return true;
    } else if (sequence[currentSize - 1] !=  endIndex) {
        //if the last element of the sequence does not reach the end index, just increment it 
        sequence[currentSize - 1] ++;
        return true;
    } else if (totNum == 1) {
        //if total number is one, and the last element already reaches the end index
        return false;
    } else {// At this point, the sequence contains at least two elements, and the last one already reaches
                // end index
        int i;
        int j;

        //starts at the end of the sequence and works its way towards the front, looking for two 
        //consecutive members of the sequence where the difference between them is greater 
        //than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin
        //index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
        //loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
        //If j is less than zero, it means it already reaches the last combination of current size.
        //For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
        // of combination to 5
        i = currentSize;
        j = i - 1;
        while( j >= 0 && sequence[i] == sequence[j] + 1){
            i--;
            j = i -1;
        };

        if (j < 0) { //reaches the last combination of current size

            if (currentSize == totNum) {
                //if the current size equals to total number, done
                return false;
            } else {

                //push the first currentSize+1 element into sequence 
                for(int i = 0; i < currentSize; i++)
                    sequence[i] = beginIndex + i;
                sequence.push_back(beginIndex + currentSize);
                
                return true; 
            }            
        } else {
            ++sequence[j];

            for(int k = j + 1; k < currentSize; k++)
                sequence[k] = sequence[k-1] + 1; 

            return true;
        }
        
        
    }
    
}

} //end namespace oopse
#endif //UTILS_GENERATECOMBINATION_HPP
Revision:	1665
Committed:	Thu Oct 28 06:23:42 2004 UTC (19 years, 8 months ago) by tim
File size:	4131 byte(s)
Log Message:	bug fixed in GenerateCombination.hpp
#	Content
1	/*
2	* Copyright (C) 2000-2004 Object Oriented Parallel Simulation Engine (OOPSE) project
3	*
4	* Contact: oopse@oopse.org
5	*
6	* This program is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU Lesser General Public License
8	* as published by the Free Software Foundation; either version 2.1
9	* of the License, or (at your option) any later version.
10	* All we ask is that proper credit is given for our work, which includes
11	* - but is not limited to - adding the above copyright notice to the beginning
12	* of your source code files, and to any copyright notice that you may distribute
13	* with programs based on this work.
14	*
15	* This program is distributed in the hope that it will be useful,
16	* but WITHOUT ANY WARRANTY; without even the implied warranty of
17	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18	* GNU Lesser General Public License for more details.
19	*
20	* You should have received a copy of the GNU Lesser General Public License
21	* along with this program; if not, write to the Free Software
22	* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23	*
24	*/
25
26	/**
27	* @file GenerateCombination.hpp
28	* @author tlin
29	* @date 10/27/2004
30	* @version 1.0
31	*/
32
33	#ifndef UTILS_GENERATECOMBINATION_HPP
34	#define UTILS_GENERATECOMBINATION_HPP
35
36	#include <vector>
37
38	namespace oopse {
39	//this algorithm can be modified to be compatible with STL container
40	//Basically, changes totNum to last iteratir and beginIndex to first iterator, sequence from
41	//a vector<int> to a vector<iterator>, STL compatible version will be committed next time
42	bool next_combination(std::vector<int> sequence, int totNum, int beginIndex = 0) {
43	int endIndex = beginIndex + totNum - 1;
44	int currentSize;
45	currentSize = sequence.size();
46
47	if (currentSize == 0) {
48	//if sequence is empty, we push the begin index into it
49	sequence.push_back(beginIndex);
50	return true;
51	} else if (sequence[currentSize - 1] != endIndex) {
52	//if the last element of the sequence does not reach the end index, just increment it
53	sequence[currentSize - 1] ++;
54	return true;
55	} else if (totNum == 1) {
56	//if total number is one, and the last element already reaches the end index
57	return false;
58	} else {// At this point, the sequence contains at least two elements, and the last one already reaches
59	// end index
60	int i;
61	int j;
62
63	//starts at the end of the sequence and works its way towards the front, looking for two
64	//consecutive members of the sequence where the difference between them is greater
65	//than one. For example , if the sequence contains 1, 5, 8, 9 (total number is 10, begin
66	//index is 0, therefore 9 is the end index, and the current size is 4). At the end of while
67	//loop, j will point to 5, and i will point to 8, next combination should be 1, 6, 7, 8.
68	//If j is less than zero, it means it already reaches the last combination of current size.
69	//For instance, sequence may contain 6, 7, 8, 9 at this time, we need to increase the size
70	// of combination to 5
71	i = currentSize;
72	j = i - 1;
73	while( j >= 0 && sequence[i] == sequence[j] + 1){
74	i--;
75	j = i -1;
76	};
77
78	if (j < 0) { //reaches the last combination of current size
79
80	if (currentSize == totNum) {
81	//if the current size equals to total number, done
82	return false;
83	} else {
84
85	//push the first currentSize+1 element into sequence
86	for(int i = 0; i < currentSize; i++)
87	sequence[i] = beginIndex + i;
88	sequence.push_back(beginIndex + currentSize);
89
90	return true;
91	}
92	} else {
93	++sequence[j];
94
95	for(int k = j + 1; k < currentSize; k++)
96	sequence[k] = sequence[k-1] + 1;
97
98	return true;
99	}
100
101
102	}
103
104	}
105
106	} //end namespace oopse
107	#endif //UTILS_GENERATECOMBINATION_HPP