c/c++ permtation file

February 23, 2010 9:49 AM

I need to write a program in C/C++ that takes all the permutations of a set of numbers, say {1,2,3,4}, and puts them in a binary file.

I have found quite a few algorithms on the internet that get the permutations and display them, but I need them in a file. For instance there are 24 permutations of {1,2,3,4} and so I would like to set up an array that is 96 (24*4) elements long, with every four being a new permutation, which I then write to a file. The one at the bottom of this page seems to work, I just don't know how to get them all in a file. Any thoughts?

posted by amsterdam63 to computers & internet (15 answers total)

I'm sorry, here's the code that actually works to get them displayed, but again, I'm not sure how to get them in a file:

#include
#include

void print(const int *v, const int size)
{
if (v != 0) {
for (int i = 0; i <> printf("%4d", v[i] );
}
printf("\n");
}
} // print


void visit(int *Value, int N, int k)
{
int static level = -1;
level = level+1; Value[k] = level;

if (level == N)
print(Value, N);
else
for (int i = 0; i <> if (Value[i] == 0)
visit(Value, N, i);

level = level-1; Value[k] = 0;
}


int main()
{
const int N = 4;
int Value[N];
for (int i = 0; i <> Value[i] = 0;
}
visit(Value, N, 0);
system("pause");
}
posted by amsterdam63 at 9:53 AM on February 23, 2010

So, what you're saying is that you need to know how to write to a file in C/C++? Isn't that relatively trivial?
posted by tmcw at 9:53 AM on February 23, 2010

Like this? (from)
posted by tmcw at 9:54 AM on February 23, 2010

#include <fstream>

ofstream stream("filename");
stream.write(buffer, size);
posted by equalpants at 10:05 AM on February 23, 2010

Need more information. Binary, ASCII? Does integer size or byte ordering matter? Is this homework?
posted by ldenneau at 10:05 AM on February 23, 2010

...uh, or use the << operator instead of write() if you're looking to write a text file.

stream << some_number << endl;
posted by equalpants at 10:08 AM on February 23, 2010

{[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4],...} correct?

so you have an array or arrays?

seems easy. Just do two for loops, one inside the other, and inside just print out the data to the file.
for (int i = 0; i <> }
for (int j = 0; j <> }
//write array[i][j] to file
}
}
posted by zombieApoc at 10:20 AM on February 23, 2010

wow. i guess the code got bastardized when i posted it.

you get the idea
posted by zombieApoc at 10:21 AM on February 23, 2010

Yea, I know how to write to a file, but for some reason it's not working when I put it in this program. I don't think this program actually fills out an entire array of 96 elements, it just refills the Value[] array and then displays it's 4 contents over and over.

It would be a binary file, and integer size and byte order don't matter. It's not homework, just something I'm trying to figure out.
posted by amsterdam63 at 10:22 AM on February 23, 2010

Quick method for starters: declare a global array that's big enough to hold all the permutations, and also a global counter to keep track of the "current location" in the array. In your existing print() function, store the permuation in the array at the "current location" and then advance the counter. At the end of your main(), print the entire array at once using ofstream::write().

Better method: pass the big array and current-location-counter as parameters through visit() and print(), instead of making them global.

Even better way: use std::vector instead of arrays.
posted by equalpants at 10:35 AM on February 23, 2010

Where are you trying to right it to the file? If you're trying to do it in main, then yeah, it won't work.

The program uses a recursive algorithm that builds sets of arrays at each level and displaying them using the print() function. The arrays are not passed back up at the end of each recursion.

You should be looking to do the disk IO in the print() function. Maybe open a file in main, pass the stream down to the visit function (and have visit call itself subsequently with the stream) and finally pass it on to the print function for usage.

Look at file IO in C++ from the various advice given in this thread and pass the stream as reference (ofstream &stream) to each function.
posted by teabag at 10:40 AM on February 23, 2010

s/right/write/ :(
posted by teabag at 10:41 AM on February 23, 2010

If you have a program that can display what you want to the screen, you can redirect the output of that program to a file.
posted by Jpfed at 11:35 AM on February 23, 2010

No, you don't want to fill an array.

You want to do this:

while( more permutations)
. permute
. write it out
. loop


There's a very easy way to do this, using the STL, but I imagine that would defeat the purpose of your homework assignment, which I suspect wants you to do an in-place permuting using swapping.
posted by orthogonality at 1:40 PM on February 23, 2010

More hints: C file writing writes from a buffer, you pass a file pinter, the start of the buffer, and the length of the buffer. In-place permutation means that you'd always be writing the same buffer, permuting the buffer between writes:

bool permute(int*, int length);

int buf[4];
fd = creat("filename");

if( fd > 0)
while (permute(buffer, 4)) {
. write(fd, buf, 4);
}
posted by orthogonality at 1:45 PM on February 23, 2010