Generating Permutations

[Vidgie65]

These are the last few errors in my code that I am having issues with. Please provide some direction or thought as to what to do to fix it.

generator.cpp(11) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
generator.cpp(11) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
generator.cpp(63) : fatal error C1004: unexpected end-of-file found

The original assignment :
Write a program that produces ten random permutations of the numbers 1 to 10. To generate a random permutation, you need to fill a vector with the numbers 1 to 10 so that no two entries of the vector have the same contents. You could do it by brute force, by calling rand_int until it produces a value that is not yet in the vector. Instead, you should implement a smart method.

Make a second array and fill it with the numbers 1 to 10. Then pick one of those at random, remove it, and append it to the permutation vector.

Repeat ten times.

#include <string>
#include <vector>

using namespace std;

class PermutationGenerator
{
public:
	std::vector<int> randPermutation;
	std::vector<int> intList;
	Random ;*randSelection;
	int listSize;

	PermutationGenerator() //this(10);
	{
	}

	PermutationGenerator(int lsize)
	{
		randSelection = new Random();
		listSize = lsize;
		intList = std::vector(listSize);
		randPermutation = std::vector(listSize);
	}

	virtual std::vector<int> nextPermutation()
	{
		// Fill the ArrayList intList with the numbers 1 to 10

		intList.clear();
		for (int i = 1; i <= listSize; i++)
			intList.push_back(i);

		randPermutation.clear();
		for (int i = 1; i <= listSize; i++)
		{
		// Pick a number at random using (using Random.nextInt(int), 
		// that removes a number from the intList.
			int index = randSelection->nextInt(intList.size());
			int number = intList.remove(index);

		// Add and append the random number to the randPermutation ArrayList. 
		// Repeated listSize times
			randPermutation.push_back(number);
		}

		return randPermutation;
	}

	static void main(std::string args[])
	{
		//  Prints out the values of the returned ArrayList
		PermutationGenerator *gen = new PermutationGenerator(10);
		for (int i = 1; i <= 10; i++)
		{
			std::cout::put("List " + i + ": ");
			std::vector<int> list = gen->nextPermutation();
			puts(list);
		}
	}

}

[mrnutty]

>>Random ;*randSelection;

what do you think this means? I assume you want int randomSelection .

And add a semicolon after '}' in line 62

[L7Sqr]

I think it is good that you worked through this example by hand to see how to work with the containers; it is an invaluable experience, doing something by hand.

Now that you are [mostly] done however, I'd suggest you have a look at something like std::random_shuffle and how that might simplify your design a bit.

[mrnutty]

Also I just realize your using somewhat java with this. There is no static void main. What you want is this :

#include <vector>
using namespace std;
class YourClass{
 //...
};
int main(){
 //your main 
}

[mike_2000_17]

Is this the Java forum? I'm confused... no, it is the C++ forum. Please post your code in the appropriate programming language for the forum!

Whatever Random is, I assume it is a class that you wrote or your prof gave you as part of the assignment, because it is not part of C++ standard libraries (I just wanted to point that out because there are many clues in your code that suggest you are a Java programmer). To generate random numbers in C++, you can use rand() (and srand() to seed it), or any random number generator for the <random> library (may not yet be supported by your compiler, it is from the upcoming C++ standard).

The "Fatal Error" is due to either the fact that most C/C++ compilers require an empty line at the end of the code (so you need to leave at least one empty line at the end), or it is due to the fact that you don't have a main() function. The main() function you have is a static member function. This is not C++ (it is Java). A main function in C/C++ is like so:

//free-function
int main() { //must return a value of type 'int'
  //insert code here..
  return 0; //return 0 if all went well, otherwise return an error-code of your choice.
}

//the other alternative is to capture the command-line arguments as well:
//int main(int argc, char** argv) {

Second, you shouldn't have a default constructor that doesn't initialize your data members, because that will lead to having an object filled with garbage values. The easiest way to handle this is to use a parametrized constructor with default values for the parameters, as so:

PermutationGenerator(int lsize = 10) //the default constructor assumes 10 elements in the list.

This way you can remove the default constructor and save a few lines of code and code duplication, and you guarantee that your object is properly initialized.

Third, another Java-related error, you did not provide a destructor for your object, yet one of your data members is dynamically allocated (the 'Random' data member). This is a memory-leak. C++ does not implement garbage collection (like Java does), you are responsible for sealing your code tight and avoid leaks. So, you should clean up with a destructor. In a destructor, you don't need to clean up any data member that is held by value in your class, but you do need to free any memory that your class has allocated, so you would need this:

~PermutationGenerator() {
      delete randSelection;
    };

However, just to contradict what I just said, you should not have to have a destructor here because the lifetime of your 'randSelection' data member is the same as the lifetime of your 'PermutationGenerator' object. This data member really ought to be held by value in your 'PermutationGenerator' class. I know that value-semantics is not so obvious to Java programmers, but it is mighty useful as it enables what is arguably the most powerful idiom in OOP, that is, Resource Acquisition Is Initialization (RAII). So, in this case, you could simply hold randSelection as an object of class Random, not as a pointer to one (that is, if you need it at all, as I said, in C++, you use rand() function to generate random numbers). In this case, you won't need a destructor since all data members are held by value in the class, and will be destroyed automatically along with your 'PermutationGenerator' object.

Fourth, there is no function called remove() in the std::vector class template. Check the reference pages. You need to use erase(). And you need to retrieve the value before you erase it. And you need to do the erase with an iterator (use v.erase(v.begin() + index); , where v is the vector and index is the index of the element to remove).

Fifth, to do trivial initializations in a constructor, C++ has a mechanism called an "initialization list" which allows you to call the constructors for all your data members in a comma-separated list. You start the initialization list with a colon after the close parenthesis of the constructor's prototype and put the list before the opening curly brace. As so:

PermutationGenerator(int lsize = 10) : randPermutation(lsize), 
                                           intList(lsize),
                                           randSelection(),
                                           listSize(lsize) { /* empty */ }

Finally, you do not need to hold two lists of numbers in your class. This is because the intList is only used temporarily and thus, is not required to exist beyond the "nextPermutation" function scope. Furthermore, think about this for a moment. Does the list from which you pick out the numbers (intList) really need to have numbers from 1 to 10 in order? If no, can't the last permuted sequence serve as the input for obtaining the next one? If yes, do you really need to clear or delete the last permuted sequence and then fill it from data picked off a fresh intList? If no, then you could use the following technique instead:

virtual const std::vector<int>& nextPermutation() //return a const ref instead.
    {
      // Reuse the last permuted sequence, and put it in a temporary vector:
      std::vector<int> intList; //intList is empty at this point.
      intList.swap(randPermutation); //swap with randPermutation.
      //at this point, randPermutation is empty and intList contains all numbers from 1 to 10 (not in order).

      for (int i = 1; i <= listSize; i++)
      {
        int index = randSelection->nextInt(intList.size());

        randPermutation.push_back(intList[index]); //append the number.

        intList.erase(intList.begin() + index); //remove it from intList.
      }

      return randPermutation;
    }

To use the above, you do need to initialize the randPermutation vector to hold all the numbers from 1 to 10, but you only need to do that once in the constructor. Your intList data member is no longer needed. And I would also recommend you make all the data members private, as they should not be tampered with by the user of this class.

If you implement all of the above, you will start to be on your way out of the horrors of Java and into the magical world of C++. And later you will realise that C++ already has a function called std::random_shuffle that does exactly this, but better.