Find all Permutations of a list

[spano693]

I need to find all the possible permutations of a list and I am completely stumped. The specification for the function is:

void allPerms(intListType *toOrigList, intListType *answer)
 

where *toOrigList is a pointer to a list and *answer is an array of lists. intListType has several member functions and I will post them if you want them, but for the most part they are barely used in this function (which is not a member function). I'm having trouble outputting the permutations because the program keeps crashing. I cannot change the specification of the function and if you want the rest of the program I will post it. Anyway, here is what I have of the function so far:

#include "allPerms.h"
#include <string>
#include <cstddef>
#include <iostream>
using namespace std;
 
void allPerms(intListType *toOrigList, intListType *answer)
//Pre: list is not empty
//Post: computes all permutations of a given list
{
    int length = toOrigList->getLength();
 
    if(length == 1){
        toOrigList->copyTo(&answer[0]);
    }
    else{
        toOrigList->resetList();
 
        for(int i = 0; i < length; i++){
            intListType smallerList;
            int amount = factorial(length-1);
            intListType array[amount];
            int first = toOrigList->getNextInt();
 
            toOrigList->copyTo(&smallerList);
            smallerList.deleteInt(first);
            allPerms(&smallerList, array);
 
            for(int j = 0; j < amount; j++){
                array[].copyTo(&answer[]);
            }
        }
    }
}
 
int factorial(int n)
//Pre: enter integer
//Post: returns factorial of number
{
    int answer;
 
    if(n < 0){
        throw string("no factorial for numbers less than 0");
    }
    else if(n == 0){
        answer = 1;
    }
    else{
        answer = n*factorial(n-1);
    }
 
    return answer;
}
 

Thank you for any help you may be able to provide!

[spano693]

array[].copyTo(&answer[]);<----the arrays are empty because I don't know what to put in them to get it to work properly

[weaknessforcats]

First, you are dealing with permutations rather than combinations. So each permutation is an ordered variation of the original set. Like 4321 is a permutation of 1234 but 432 is not.

That said, this code:

intListType array[amount];

requires intListType to have a cnstructor to initialize the array. But each element of the array musy be allocated enought memory to hold a permutation. This implies intListType knows the number of elements in the permutation. This will be hard to do with no argument for it.

Also this code:

intListType array[amount];

shows allocation on the stack. Stack memory is limited an this sort of thing can cause a crash.You should do all of your allocations on the heap using the "new" operator.

There are n! permutations of a set. So your answers can be in an array of n! elements provided each element is allocated (on the heap) a size equal to the size of the original set. You need to do this before copying stuff around.

[spano693]

So you're saying that I should make all the arrays like this?

intListType array = new intListType[amount];
 

Also, do you want me to post my intListType class or the constructor for it?

[weaknessforcats]

Yes, you should do that but also each element of array will hold a permutation so you need to allocate memory for each element. Since i don't have your code look at this:

1) assume my permutation set is 10 integers.
2) So I need an aray of 10! elements where each element is itself an array of 10 int.
3) 10! is 3,628,800

int (*array)[10] = new int[3628800][10];

Now array[0] is an array of 10 int and array[0] can hold one permutation.

In this scheme individual elements of the permutation would be
array[0][i] where i varies from 0 to 9.

Of course, since this is C++ you should be using vector since vector is implemented as an array. However, I didn't want to muddy the water with refinements when the code is not yet working.

For more info on how this array is allocated read: http://bytes.com/topic/c/insights/77...rrays-revealed

[spano693]

First off, very nice article I wish I knew about that when I was learning multidimensional arrays. Secondly, I'm getting confused because I'm new to programming and very new to using recursion. I'm trying to make variables to do what you suggested and I can't because I'm having trouble tracking what my code is doing. Right now I gave my array constant values, but I don't think that works do to the nature of my program. If I have: (using a list of 1,2,3)

intListType (*array)[3] = new intListType[6][3];

I get a compile error. Here is my code so you can give me a more concrete example/directions if you're up to it. I appreciate your help and thank you if you feel like reading through all this.

intList.h

#include <string>
using namespace std;
 
struct nodeType;
 
class intListType
{
    public:
        intListType();
        int getLength();
        void putInt(int x);
            //Pre: x is not already in list
            //Post: insert x at the head of the list
        void resetList();
            //PostL set current location to be off the end of the list
        int getNextInt();
            //Pre: list has not been changed since last reset
            //     current location is not the end of the list
            //Post: advance current location and return int at next location
        void deleteInt(int x);
            //Pre: x is on the list
            //Post: delete x
        bool isIn(int x);
            //Pre: list was initialized
            //Post: returns true or false if x in list
        void copyTo(intListType *toNew);
        string toString();
        ~intListType();
            //Post: free up the memory used by the list
            //      and set the header of the list to NULL
    private:
        nodeType* listHead;
        nodeType* currentLocation;
            //points to a node in the list, or NULL if off the end of the list
        int length;
};
 

intList.cpp

#include <string>
#include "intList.h"
#include <cstddef>
#include <sstream>
#include <iostream>
 
using namespace std;
 
struct nodeType
{
    int info;
    nodeType* next;
};
 
intListType::intListType()
{
    length = 0;
    listHead = NULL;
    currentLocation = NULL;
}
 
int intListType::getLength()
{
    return length;
}
 
void intListType::putInt(int x)
    //Pre: x is not already in list
    //Post: insert x at the head of the list
{
    nodeType* toLocation;
    toLocation = new nodeType;
    (*toLocation).info = x;
    (*toLocation).next = listHead;
    listHead = toLocation;
    length = length + 1;
}
 
void intListType::resetList()
    //PostL set current location to be off the end of the list
{
    currentLocation = NULL;
}
 
int intListType::getNextInt()
    //Pre: list has not been changed since last reset
    //     current location is not the end of the list
    //Post: advance current location and return int at next location
{
    if(currentLocation == NULL){
        currentLocation = listHead;
    }
    else{
         currentLocation = currentLocation->next;
        if(currentLocation == NULL){
            throw string("Attempt to getNextInt when next is the last entry in last");
        }
    }
    return (*currentLocation).info;
}
 
 
void intListType::deleteInt(int x)
    //Pre: x is on the list
    //Post: delete x
{
    nodeType *prevNode = listHead;
    currentLocation = listHead->next;
 
    if(x == listHead->info){
        nodeType *oldNode = listHead;
        listHead = listHead->next;
        delete oldNode;
    }
    else{
        while(!(currentLocation->info == x)){
            prevNode = currentLocation;
            currentLocation = currentLocation->next;
            if(currentLocation == NULL){
                throw string("Item to be deleted was not found");
            }
        }
        nodeType *nodeToDel;
        nodeToDel = currentLocation;
        prevNode->next = currentLocation->next;
    }
    length--;
}
 
bool isInRec(nodeType *toHead, int x); //declaration
bool intListType::isIn(int x)
{
    return isInRec(listHead, x);
}
bool isInRec(nodeType *toHead, int x)
{
    bool answer;
 
    if(toHead == NULL){
        answer = false;
    }
    else if(toHead->info == x){
        answer = true;
    }
    else{
        answer = isInRec(toHead->next, x);
    }
 
    return answer;
}
 
string toStringRec(nodeType *toNode); //declaration
string intListType::toString()
{
    return toStringRec(listHead);
}
string toStringRec(nodeType *toNode)
{
    stringstream s;
    if(toNode != NULL){
        s << toNode->info << '\t';
        s << toStringRec(toNode->next);
    }
    return s.str();
}
 
void copyToRec(intListType *toNew, nodeType *toHead);
void intListType::copyTo(intListType *toNew)
{
    copyToRec(toNew, listHead);
}
void copyToRec(intListType *toNew, nodeType *toHead)
{
    if(toHead != NULL){
        toNew->putInt(toHead->info);
        copyToRec(toNew, toHead->next);
    }
}
 
 
void destroyRec(nodeType *toNode);
intListType::~intListType()
{
    destroyRec(listHead);
}
void destroyRec(nodeType *toNode)
{
    if(toNode == NULL){
        //do nothing
    }
    else{
        destroyRec(toNode->next);
        delete toNode;
    }
}
 

allPerms.h

#include "intList.h"
 
void allPerms(intListType *toOrigList, intListType *answer);
//Pre: list is not empty
//Post: computes all permutations of a given list
 
int factorial(int n);
//Pre: enter integer
//Post: returns factorial of number
 

allPerms.cpp

#include "allPerms.h"
#include <string>
#include <cstddef>
#include <iostream>
using namespace std;
 
void allPerms(intListType *toOrigList, intListType *answer)
//Pre: list is not empty
//Post: computes all permutations of a given list
{
//    int length = toOrigList->getLength();
//
//    if(length == 1){
//        toOrigList->copyTo(&answer[0]);
//    }
//    else{
//        toOrigList->resetList();
//
//        for(int i = 0; i < length; i++){
//            intListType smallerList;
//            int amount = factorial(length-1);
//            intListType array[amount];
//            int first = toOrigList->getNextInt();
//
//            toOrigList->copyTo(&smallerList);
//            smallerList.deleteInt(first);
//            allPerms(&smallerList, array);
//
//            for(int j = 0; j < amount; j++){
//                array[].copyTo(&answer[]);
//            }
//        }
//    }
    int length = toOrigList->getLength();
 
    if(length == 1){
        toOrigList->copyTo(&answer[0]);
    }
    else{
        toOrigList->resetList();
 
        for(int i = 0; i < length; i++){
            intListType smallerList;
            int amount = factorial(length-1);
            intListType (*array)[6] = new intListType[3][6];
            int first = toOrigList->getNextInt();
 
            toOrigList->copyTo(&smallerList);
            smallerList.deleteInt(first);
            allPerms(&smallerList, array);
 
            for(int j = 0; j < amount; j++){
                array[i][j].copyTo(&answer[i]);
            }
        }
    }
}
 
int factorial(int n)
//Pre: enter integer
//Post: returns factorial of number
{
    int answer;
 
    if(n < 0){
        throw string("no factorial for numbers less than 0");
    }
    else if(n == 0){
        answer = 1;
    }
    else{
        answer = n*factorial(n-1);
    }
 
    return answer;
}
 

allPermsDr.cpp

#include "allPerms.h"
#include <iostream>
using namespace std;
 
void guts()
{
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;
    cout << endl;
 
    intListType aList;
    aList.resetList();
    for(int i = 1; i <= n; i++){
        aList.putInt(i);
    }
 
    intListType *allPermutations;
    int f = factorial(n);
    allPermutations = new intListType[f];
    allPerms(&aList, allPermutations);
 
    for(int p = 0; p < f; p++){
        cout << (allPermutations[p]).toString() << endl;
    }
}
 
int main()
{
    try{
        guts();
    }catch(string message){
        cout << "Exception thrown: " << message << endl;
    }
}
 

Thank you

[weaknessforcats]

Your code compiles for me on Visual Studio.NET 2008.

But I had to make one change: You are missing a semicolon at the end of the struct nodeType definition.

Plus in C++ to define an array of class intListType objects you need both a default constructor and a destructor. I used your default ctor but had to code a dtor.

[spano693]

Wait so with those changes, if you inputted 3 it would output:
123
213
312
and so on?
I know they program can compile without any errors, but when it runs I'm fairly confident its getting a segmentation fault or something like that because it just crashes (my compiler doesn't tell me)

[weaknessforcats]

This would be an excellent time to start using your debugger and stepping through the code.

Use a small permutaion set, like 3 so there are few permutations.

As you step through be sure all your variables contain the expected values.

Nothing "just crashes" and your debugger will lead to right to the problem.

As to the set 123, the permutations are:

123
213
231
321
132
312

There are 3! permutations.

[spano693]

ok Thank you very much