11 Replies - 22876 Views - Last Post: 24 March 2009 - 07:28 PM Rate Topic: -----

#1 dwayne  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 56
  • Joined: 02-August 08

Permutations and Combinations in C++

Posted 02 August 2008 - 07:21 PM

I am making a little permutation/scrambler app and this is a key part of the code. If someone knows a simple way to find all possible combinations of a string including those that are shorter than the string input, please let me know. Right know I am just running several permutations and alternating the characters input so that all characters are used.

Example, 1234 are input, run permutations of --
    234
    134
    124
    123
This is simple when dropping only one character but when dropping 4 from a string of 6... it's a lot of combinations to do manually.

This post has been edited by dwayne: 02 August 2008 - 10:41 PM


Is This A Good Question/Topic? 1

Replies To: Permutations and Combinations in C++

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Permutations and Combinations in C++

Posted 02 August 2008 - 07:23 PM

Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.

Please post like this:

Thank you for helping us helping you.
Was This Post Helpful? 0
  • +
  • -

#3 dwayne  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 56
  • Joined: 02-August 08

Re: Permutations and Combinations in C++

Posted 02 August 2008 - 07:40 PM

I must warn, it is not that good, but...

#include <string>
using namespace std;

void swap(char* first, char* second)
{
		char ch = *second;
		*second = *first;
		*first = ch;
}

int permute(char* set, int begin, int end)
{
	int i;
	int range = end - begin;
	if (range == 1) {
			cout << set << endl;
	} else {
			for(i=0; i<range; i++) {
					swap(&set[begin], &set[begin+i]);		//initial swap
					permute(set, begin+1, end);				//recursion
					swap(&set[begin], &set[begin+i]);	   //swap back
			}
	}
	return 0;
}

int permutate5(char* p6)
{
	//declare string for 5 character permutations
	char p5[6] = {p6[1], p6[2], p6[3], p6[4], p6[5], p6[6]}; //exclude element 0
	  permute(p5, 0, strlen(p5)); //calculate
		//reset variable will go here and element one of p6 will be excluded
	return 0;
}


int main()
{
	char str[7]; //main string
	cout << "Please enter a string: ";
	cin.getline(str, 7); //take string
	cout << "Permutating \"" << str << "\"" << endl;
	  permute(str, 0, strlen(str)); //permute the string
	cout << "Calculated all possible 6 character permutations  of \"" << str << "\"" << endl;
	   //permutate 2-5 will go here when completed

}


BTW, this is a "personal" project, not my homework. If it were homework, it would be an awful weird assignment. Well, there's the code, so...

Also, how is the source code related to resetting a char variable/pointer?

This post has been edited by dwayne: 02 August 2008 - 07:44 PM

Was This Post Helpful? 0
  • +
  • -

#4 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Permutations and Combinations in C++

Posted 02 August 2008 - 08:05 PM

It's not--however without knowing whether or not its was homework in my previous post, I am required to say the site rules. Having that said:

Here is some code I wrote for string permutation in C++:

/*
 * KYA
 * String Permutation
 * @ params: char array, begin, and end of array
 * 7-21-08
 */

#include <iostream>
#include <string>
using namespace std;

void swap(char* first, char* second)
{
        char ch = *second;
        *second = *first;
        *first = ch;
}

int permute(char* set, int begin, int end)
{
        int i;
        int range = end - begin;
        if (range == 1) {
                cout << set << endl;
        } else {
                for(i=0; i<range; i++) {
                        swap(&set[begin], &set[begin+i]);		//initial swap
                        permute(set, begin+1, end);				//recursion
                        swap(&set[begin], &set[begin+i]);       //swap back
                }
        }
        return 0;
}

//Example Implementation -- Up to you on how to use
int main()
{
        char str[255]; //string 
	cout << "Please enter a string: ";
	cin.getline(str, 255); //take string
        permute(str, 0, strlen(str)); //permutate the string
        return 0;
}



edit: You already have string permutes down. Why not just create a new array/string for your thing?

Alternately, I would create a c style string (char array) and only run a loop from the beginning to whatever end point you want.

Another option is setting the pointer back to the original value and using ptr arithmetic go to whatever place you would like.

//some control structure
permute(str, 0, strlen(str-1))
//so on and so forth



Also, thats not really good programming practice.

This post has been edited by KYA: 02 August 2008 - 08:08 PM

Was This Post Helpful? 1
  • +
  • -

#5 dwayne  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 56
  • Joined: 02-August 08

Re: Permutations and Combinations in C++

Posted 02 August 2008 - 08:53 PM

View PostKYA, on 2 Aug, 2008 - 08:05 PM, said:

edit: You already have string permutes down. Why not just create a new array/string for your thing?

I am not sure what you mean? I am still sending the new array to the same function.

View PostKYA, on 2 Aug, 2008 - 08:05 PM, said:

Alternately, I would create a c style string (char array) and only run a loop from the beginning to whatever end point you want.

How do I do this?


View PostKYA, on 2 Aug, 2008 - 08:05 PM, said:

Another option is setting the pointer back to the original value and using ptr arithmetic go to whatever place you would like.

A bit complicated for my purposes, but it is an option.

View PostKYA, on 2 Aug, 2008 - 08:05 PM, said:

//some control structure
permute(str, 0, strlen(str-1))
//so on and so forth



Also, thats not really good programming practice.

This does not work for me, it outputs nothing and when I feed it a fixed variable it just gives fewer results but still with 6 letters.


Also, is there a truly better way to cut down the length without cutting out any possible results? If I read all this correctly then you are still using my method.
Was This Post Helpful? 0
  • +
  • -

#6 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Permutations and Combinations in C++

Posted 02 August 2008 - 09:26 PM

Hmm, I reread your post and you seem to just want to display all possible string permutations, in which case either yours or my code will work just fine for any number of chars within a string.


From one of your above posts:

Quote

//declare string for 5 character permutations

Was This Post Helpful? 0
  • +
  • -

#7 dwayne  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 56
  • Joined: 02-August 08

Re: Permutations and Combinations in C++

Posted 02 August 2008 - 09:58 PM

I don't believe you are understanding now. I need to input 6 letters, it needs to output every possible combination that can be made with those letters down to 2 letter combinations. Also, how do I go about setting a new value to a char array?

EDIT: I fixed the problem of editing the array, I am use to programming in C# but am trying to move to C++ so...

This post has been edited by dwayne: 02 August 2008 - 10:17 PM

Was This Post Helpful? 0
  • +
  • -

#8 dwayne  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 56
  • Joined: 02-August 08

Re: Permutations and Combinations in C++

Posted 03 August 2008 - 01:01 PM

Problem solved, I used next_combination along with that bit of permutation code and stuck it in a do-while loop with the next_combination as an argument. It required a new array for every length though that probably could be overcome but right now it will spit out 1950 results in about a second so...

I may post a good tutorial later once I get my program up and running. Thanks for all your help.
Was This Post Helpful? 0
  • +
  • -

#9 mslider  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 16-October 08

Re: Permutations and Combinations in C++

Posted 16 October 2008 - 07:20 AM

Hi
OK heres my assignment question- Write a program that, given n and alphabet Z as inputs, outputs all strings of length n over the alphabet Z.

now alphabet here means a string array where for example Z = {a, c} can be an alphabet of 2 symbols and if I want to out all the strings of length 3, this is what I should get (9 strings in total) -
aaa
aac
aca
caa
acc
cac
cca
ccc

Now i dont have any code as I am still struggling with concepts... First idea I had in mind was like to do a matrix of width n and length = total number of strings.... but, then how do I fill up the matrix??

I have no idea how to approach this problem - there is another idea i came up with which was like initialising the sequence of length n to the first symbol of the alphabet ..But again how would I come around to changing the sequence - I cant figure it out.. any ideas??
Was This Post Helpful? 0
  • +
  • -

#10 immila  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 23-November 08

Re: Permutations and Combinations in C++

Posted 23 November 2008 - 12:51 PM

I am having exactly the same problem.
Is any body can help.
I am able to do the normal permutation
Was This Post Helpful? 0
  • +
  • -

#11 aricab25  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 24-March 09

Re: Permutations and Combinations in C++

Posted 24 March 2009 - 07:24 PM

View PostKYA, on 2 Aug, 2008 - 06:23 PM, said:

[rules][/rules]


Yes Kya this is my code for a student database.I'm having problems searching for information and updating(inserting and deleting) information. [size=1]
//
// Student database program to:
// List student names
// Calculate Average age
// Calculate individual GPA up to five courses
// Search and find records
// Update records
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM1 10.0



struct student{ //Structure is defined//
char name[20];
int age;
float gpa;
int eng115;
int mst211;
int act110;
int csi212;
int mng120;
};

float CalcGpa (float x)
{
return (x*4)/20;
}

int main(void)
{
struct student info[10]; //structure is declared//
struct student *ptr; // Pointer *ptr is declared to structure//
ptr = &info[0]; //Pointer is assigned the address of the array//
ptr++;
char back;
int n,i,option;
int sum = 0;
float result,gpa;
char name[20];




strcpy(info[0].name,"Suzy Ormon");
info[0].age = 18;
info[0].gpa = 2.6;
info[0].eng115 = 2;
info[0].mst211 = 4;
info[0].act110 = 1;
info[0].csi212 = 2;
info[0].mng120 = 4;

strcpy(info[1].name,"Peter Ram");
info[1].age = 26;
info[1].gpa = 3.0;
info[1].eng115 = 3;
info[1].mst211 = 3;
info[1].act110 = 3;
info[1].csi212 = 3;
info[1].mng120 = 3;

strcpy(info[2].name,"David Chow");
info[2].age = 22;
info[2].age= 2.2;
info[2].eng115 = 4;
info[2].mst211 = 1;
info[2].act110 = 1;
info[2].csi212 = 2;
info[2].mng120 = 3;

strcpy(info[3].name,"Michelle Singh");
info[3].age = 18;
info[3].gpa = 2.8;
info[3].eng115 = 3;
info[3].mst211 = 2;
info[3].act110 = 3;
info[3].csi212 = 2;
info[3].mng120 = 4;

strcpy(info[4].name,"Susan Persaud");
info[4].age = 25;
info[4].gpa = 2.6;
info[4].eng115 = 2;
info[4].mst211 = 4;
info[4].act110 = 1;
info[4].csi212 = 2;
info[4].mng120 = 4;

strcpy(info[5].name,"Michael Ellis");
info[5].age = 19;
info[5].gpa = 2.2;
info[5].eng115 = 4;
info[5].mst211 = 1;
info[5].act110 = 1;
info[5].csi212 = 1;
info[5].mng120 = 4;

strcpy(info[6].name,"Elizabeth Arden");
info[6].age = 26;
info[6].gpa = 2.6;
info[6].eng115 = 2;
info[6].mst211 = 4;
info[6].act110 = 1;
info[6].csi212 = 2;
info[6].mng120 = 4;

strcpy(info[7].name,"Troy Sanders");
info[7].age = 22;
info[7].gpa = 2.8;
info[7].eng115 = 4;
info[7].mst211 = 3;
info[7].act110 = 1;
info[7].csi212 = 2;
info[7].mng120 = 4;

strcpy(info[8].name,"Diane Keaton");
info[8].age = 24;
info[8].gpa = 2.8;
info[8].eng115 = 4;
info[8].mst211 = 3;
info[8].act110 = 1;
info[8].csi212 = 2;
info[8].mng120 = 4;

strcpy(info[9].name,"Christopher Dale");
info[9].age = 30;
info[9].gpa = 2.4;
info[9].eng115 = 2;
info[9].mst211 = 3;
info[9].act110 = 1;
info[9].csi212 = 2;
info[9].mng120 = 4;



printf(" Main Menu of Student Database\n" );
printf(" \n");
printf("Enter 1 to access students' names\n");
printf("Enter 2 for average age of class\n");
printf("Enter 3 for individual GPA \n");
printf("Enter 4 to search for information\n");
printf("Enter 5 to update information\n");
scanf ("%d",&option);
if(option==1)
{
ptr = &info[0];

for(n=0;n<10;n++)
{
printf("Student[%d]Name is : %s\n",n,ptr->name); // Pointer to the name array//
printf(" \n");
ptr++;

}
printf("\n Select enter to return to main");
getchar();
back=getchar();
back=main();
}
if(option==2)
{
for(n=0;n<10;n++)
{
sum = sum + info[n].age;
result = sum/NUM1;
}
printf("The Average age is:%1.1f\n",result);
printf("\n press any key to return to main");
getchar();
back=getchar();
back=main();
}
if(option==3)
{
for(n=0;n<10;n++)
{
sum = info[n].eng115+info[n].mst211+info[n].act110+info[n].csi212+info[n].mng120;
gpa = CalcGpa(sum); // A call from the main program to the function CalcGpa //


printf("Name of student:%s\n",info[n].name);
printf("Student gpa is:%1.1f\n",gpa);
printf(" \n");
}
printf("\n Select enter to return to main");
getchar();
back=getchar();
back=main();
}
if(option==4)
{
printf("Enter student name :");
scanf("%s",&name);
for(n=0;n<10;n++)
{

printf("Student age is:%d\n",info[n].age);
printf("Student gpa is:%1.1f\n",info[n].gpa);


printf("\n Select enter to return to main");
getchar();
back=getchar();
back=main();
}
}
if(option==5)
{
for (n=0;n<10;n++)
{
if (strcmp (info[n].name,name)==0){
printf("Please enter name to be changed\n");
gets(info[n].name);
printf("Please enter new name\n");

}

}
printf("\n Select enter to return to main");
getchar();
back=getchar();
back=main();
}





getch();
return 0;
}
Was This Post Helpful? 0
  • +
  • -

#12 Hyper  Icon User is offline

  • Banned

Reputation: 108
  • View blog
  • Posts: 2,129
  • Joined: 15-October 08

Re: Permutations and Combinations in C++

Posted 24 March 2009 - 07:28 PM

2 Aug, 2008 - 09:21 PM

Can't the semi-dead rest in peace?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1