problem with my c++ algorithm assginment

[shamila08]

hello, dear all, i have a slightly problem with my assigment algorithm as follows:

void write( int *x,  int n)
{
  if (x != 0) {
    for (int i = 0; i < n; i++) {
      printf("%4d", x[i] );
    }
    printf("\n");
  }
} // print


void swap(int *x, int i, int j)
{
  int t;
  t = x[i];
  x[i] = x[j];
  x[j] = t;
} 


void reverse(int *x, int start, int n)
{
  int tmp = x[start];
  for (int i = start; i <n-1; ++i) {
    x[i] = x[n-i-1];
	x[n-i-1] = tmp;
  }
} 


void starterequiv(int *x,  int start, int n)
{
  write(x, n);
  if (start < n) {
    int i, j;
    for (i = n-1; i > start; i--) {
      for (j = i + 1; j < n; j++) {
	    swap(x, i, j);
	starterequiv(x, i, n);
      } 
    reverse(x, i, n);
    } 
}
}


void initiate(int *x, int n)
{
  for (int i = 0; i <n; i++) {
    x[i] = i+1;
  }
} // init


void main()
{
  char buf[100];
  int n;
  printf("Enter the number of elements: ");
  fgets(buf, sizeof(buf), stdin );
  sscanf_s(buf, "%d", &n);

  if (n > 0 && n <= 100) {
    int *x = new int[n];
    initiate(x, n);
    starterequiv(x, 0, n);
  }
}

i need an output as follows:
1234
1432
1423
1324
1342
1243
. but i didnt get it. how to fix it?

many thanks.

[AceofSpades19]

don't use void main(), use int main(). void main() doesn't compile on most compilers and is incorrect according to the standard

[jencas]

What output do YOU get?? At first glance the reverse function is looking odd. Are you sure that this function is working fine? And why don't you use std::vector and std::next_permutation if you are coding in C++???

[shamila08]

What output do YOU get?? At first glance the reverse function is looking odd. Are you sure that this function is working fine? And why don't you use std::vector and std::next_permutation if you are coding in C++???

.

the reverse function is used for reverse the array such as follows
1234 then 4321. i already test it. it's find.

i didn't use next_permutation because i have to build my own algorithm as my assignment.
do you any suggestion in spite of use next_permutation?

[shamila08]

What output do YOU get?? At first glance the reverse function is looking odd. Are you sure that this function is working fine? And why don't you use std::vector and std::next_permutation if you are coding in C++???

.
Below its the output:

Enter the number of elements: 4
   1   2   3   4
   1   2   4   3
   1   2   4   3
   1   2   3   4
   1   4   2   3
   1   4   3   2
Press any key to continue . . .

The problem start after 1234, suppose it will be 1432 ( reverse except '1')
then its suppose to swap 1423, then reverse 1324 ( reverse except '1')
then its suppose to swap 1342, then its reverse 1243.

[vmanes]

The loop in reverse( ) never stores a new value of temp after the initial value. How can this reverse the full array (or subset)?

And, this is C code, not C++. Please use the correct forum.

[shamila08]

The loop in reverse( ) never stores a new value of temp after the initial value. How can this reverse the full array (or subset)?

And, this is C code, not C++. Please use the correct forum.

thanks for the comment. ok i change from reverse function to recycle function. but the idea is still same. here my algorithm

#include <stdio.h>

/**
   Read a number, n, from standard input and print the
   permutations.
 */

void write( int *x,  int n)
{
  if (x != 0) {
    for (int i = 0; i < n; i++) {
      printf("%4d", x[i] );
    }
    printf("\n");
  }
} // print


void swap(int *x, int i, int j)
{
  int t;
  t = x[i];
  x[i] = x[j];
  x[j] = t;
} 


void recycle(int *x, int start, int n)
{
  int tmp = x[start];
  for (int i = start; i <n-1; ++i) {
    x[i] = x[n-i-1];
	x[n-i-1] = tmp;
  }
} 


void starterequiv(int *x,  int start, int n)
{
  write(x, n);
  if (start < n) {
    int i, j;
    for (i = n-1; i > start; i--) {
      for (j = i + 1; j < n; j++) {
	    swap(x, i, j);
	starterequiv(x, i, n);
      } 
    recycle(x, i, n);
    } 
}
}


void initiate(int *x, int n)
{
  for (int i = 0; i <n; i++) {
    x[i] = i+1;
  }
} // init


void main()
{
  char buf[100];
  int n;
  printf("Enter the number of elements: ");
  fgets(buf, sizeof(buf), stdin );
  sscanf_s(buf, "%d", &n);

  if (n > 0 && n <= 100) {
    int *x = new int[n];
    initiate(x, n);
    starterequiv(x, 0, n);
  }
}

my output as follows:
1234
1243
1423
1432
1234
1243

which is not the output i need. i know the problem is in loop of starterequiv function which is related to integer i and j. actually in my real intention that , i need to recycle first then swap.

[shamila08]

The loop in reverse( ) never stores a new value of temp after the initial value. How can this reverse the full array (or subset)?

And, this is C code, not C++. Please use the correct forum.

sorry. here my algorithm

#include <stdio.h>

/**
   Read a number, n, from standard input and print the
   permutations.
 */

void write( int *x,  int n)
{
  if (x != 0) {
    for (int i = 0; i < n; i++) {
      printf("%4d", x[i] );
    }
    printf("\n");
  }
} // print


void swap(int *x, int i, int j)
{
  int t;
  t = x[i];
  x[i] = x[j];
  x[j] = t;
} 


void recycle(int *x, int start, int n)
{
  int tmp = x[start+1];
  for (int i = start+1; i <n-2; ++i) {
    x[i] = x[n-i-1];
	x[n-i-1] = tmp;
  }
} 


void starterequiv(int *x,  int start, int n)
{
  write(x, n);
  if (start < n) {
    int i, j;
    for (i = n-1; i > start; i--) {
      for (j = i + 1; j < n; j++) {
	    swap(x, i, j);
	starterequiv(x, i, n);
      } 
    recycle(x, i, n);
    } 
}
}


void initiate(int *x, int n)
{
  for (int i = 0; i <n; i++) {
    x[i] = i+1;
  }
} // init


void main()
{
  char buf[100];
  int n;
  printf("Enter the number of elements: ");
  fgets(buf, sizeof(buf), stdin );
  sscanf_s(buf, "%d", &n);

  if (n > 0 && n <= 100) {
    int *x = new int[n];
    initiate(x, n);
    starterequiv(x, 0, n);
  }
}

[AceofSpades19]

Don't use void main(), use int main() as I said in my previous post

[shamila08]

Don't use void main(), use int main() as I said in my previous post

yup. i just change it. but the output is not change. i think there is a problem in starterequive function. the way i write the algorithm as below is wrong.:

void starterequiv(int *x,  int start, int n)
{
  write(x, n);
  if (start < n) {
    int i, j;
    for (i = n-1; i > start; i--) {
      for (j = i + 1; j < n; j++) {
	    swap(x, i, j);
	starterequiv(x, i, n);
      } 
    reverse(x, i, n);
    } 
}
}

i need to fix it but dont know. i need your all opinion.

[VernonDozier]

I for one don't understand what the algorithm/approach is here. Aside from that, I think you should clean up the code. One, since this is C++, convert input and output to cin and cout. Two, I don't see where you use buf now, so I'd take those lines out.

[shamila08]

I for one don't understand what the algorithm/approach is here. Aside from that, I think you should clean up the code. One, since this is C++, convert input and output to cin and cout. Two, I don't see where you use buf now, so I'd take those lines out.

the algorithm approach here is base on combinatoric concept. If its difficult to analyze, so i put others algorithm as follows:

#include <stdio.h>
#include <iostream>
using namespace std;

/**
   Read a number, n, from standard input and print the
   permutations.
 */

void write( int *x,  int n)
{
  if (x != 0) {
    for (int i = 0; i < n; i++) {
      cout <<  x[i];
    }
    cout <<("\n");
  }
} 


void swap(int *x, int i, int j)
{
  int t;
  t = x[i];
  x[i] = x[j];
  x[j] = t;
} 

void starterequiv(int *x,  int start, int n)
{
  write(x, n);
  if (start < n) {
    int i, j;
    for (i = n-1; i > start; i--) {
      for (j = i + 1; j < n; j++) {
	    swap(x, i, j);
	starterequiv(x, i, n);
	swap(x,j,i);
      } 
    } 
}
}


void initiate(int *x, int n)
{
  for (int i = 0; i <n; i++) {
    x[i] = i+1;
  }
} // init


int main()
{
  int n;
  cout << "Enter the number of elements: ";
  cin >> n;

  if (n > 0 && n <= 100) {
    int *x = new int[n];
    initiate(x, n);
    starterequiv(x, 0, n);
  }
}

the output is as follows
1234
1243
1324
1342
1423
1432.
my question is how to eliminated array by using filter?
i need the output as follows:
1234
1243
1324
eliminated 1342 , 1423, 1432. the reason is 1342 = 1243, and so on.

[VernonDozier]

You seem to be pretty close. I haven't done an exhaustive search, but it appears that it lists all the permutations of digits AFTER the first digit. You appear to never swap the first digit. To prove this to yourself, add a little debugging statement to your swap function and see if it displays:

void swap(int *x, int i, int j)
{
  if (i == 0)
      cout << "I am swapping the first element!\n";
      
  int t;
  t = x[i];
  x[i] = x[j];
  x[j] = t;
}

If you never swap the first element, it'll never display. Note this line in your starterequiv function:

for (i = n-1; i > start; i--) {

Will i ever get a chance to be less than or equal to start? With the original call, start is set to equal 0. Subsequent calls to startequiv are this:

starterequiv(x, i, n);

Neither i nor start will ever equal 0, so the the 0th element will never be swapped, as far as I can tell.

[shamila08]

You seem to be pretty close. I haven't done an exhaustive search, but it appears that it lists all the permutations of digits AFTER the first digit. You Neither i nor start will ever equal 0, so the the 0th element will never be swapped, as far as I can tell.

thanks for your explanation. actually i'm little bit blur to use filter/delete/erase function. As i said before:

my output
1234
1243
1324
1342
1432
1423
.
then i have to delete the three array such as 1342, 1432, and 1423.(coincidentally its was listed in last three.) is it possible? or should i use another alternative?

[VernonDozier]

thanks for your explanation. actually i'm little bit blur to use filter/delete/erase function. As i said before:

my output 1234 1243 1324 1342 1432 1423 . then i have to delete the three array such as 1342, 1432, and 1423.(coincidentally its was listed in last three.) is it possible? or should i use another alternative?

Delete? Is deleting part of the assignment? Here's a code snippet from Dream In Code (there are some decent permutation code snippets on Daniweb too, but this one from Dream In Code seems fairly close to yours). It does use templates, but that's irrelevant to the logic of how to permute. It also explains how to run it. Like I said, it looks similar to yours. Look it over, run it (you'll have to add a main function, but it can be very short and the snippet suggests one in the comments), and see if that helps. http://www.dreamincode.net/code/snippet1438.htm

[shamila08]

Delete? Is deleting part of the assignment? Here's a code snippet from Dream In Code (there are some decent permutation code snippets on Daniweb too, but this one from Dream In Code seems fairly close to yours). It does use templates, but that's irrelevant to the logic of how to permute. It also explains how to run it. Like I said, it looks similar to yours. Look it over, run it (you'll have to add a main function, but it can be very short and the snippet suggests one in the comments), and see if that helps.

http://www.dreamincode.net/code/snippet1438.htm

.

the reason is the first three, i will use it again to generate the next array. i cant proceed because i dont now how to delete the last three from the output list. my assignment is not stop yet. Then i would like to learn how to use filter or erase function in my algorithm?

[VernonDozier]

.

the reason is the first three, i will use it again to generate the next array. i cant proceed because i dont now how to delete the last three from the output list. my assignment is not stop yet. Then i would like to learn how to use filter or erase function in my algorithm?

There's nothing to delete in the permutations. You never store the permutations, you just output each permutation, then it's lost forever as far as I can tell, or rather overwritten when the next permutation is calculated. You create exactly one array in the program and never delete it. Is the question how to delete part of a dynamic array?

int* x = new int[4];

and you want to delete elements x[1] through x[3] or something? I think you are going to have to a lot more clear about what you mean by "erase" and "filter" functions.delete the last three from the output list

I don't know what this means. The output is what you are displaying with cout. What you delete in memory and what you display are two separate concepts.delete the last three from the output list

Last three what? Last three digits from a permutation? Last three permutations? I think you need to explain exactly what the goal is on all of this because if all it is is to display all the permutations, which is what I though t it was, I don't understand where and why the deletion is needed.

[shamila08]

There's nothing to delete in the permutations. You never store the permutations, you just output each permutation, then it's lost forever as far as I can tell, or rather overwritten when the next permutation is calculated. You create exactly one array in the program and never delete it. Is the question how to delete part of a dynamic array?

int* x = new int[4];

and you want to delete elements x[1] through x[3] or something? I think you are going to have to a lot more clear about what you mean by "erase" and "filter" functions.

I don't know what this means. The output is what you are displaying with cout. What you delete in memory and what you display are two separate concepts.

Last three what? Last three digits from a permutation? Last three permutations? I think you need to explain exactly what the goal is on all of this because if all it is is to display all the permutations, which is what I though t it was, I don't understand where and why the deletion is needed.

i'm sorry for my bad explanation. it's made confusion. Actually i have to delete 1342, 1432, and 1423 in the memory such that my output will appear as follows:

1234
1243
1342

the next step. i will use discrete math concept to generate permutation based on 1234, 1243, and 1342. that's enough.

[shamila08]

Here one of my subroutine

void starterequiv(int *arr,  int start, int SIZE)
{	int count = 1;
	if (start > SIZE) 
	 print(arr, SIZE);
	else
	{ int i, j; 
		starterequiv(arr,start+1 ,SIZE);
    for (i = SIZE-1; i > start; i--) { 
      for (j = i+1 ; j <= SIZE-1; j++) {
	    swap(arr, i, j);
		starterequiv(arr, i, SIZE);
		count++ ;

      } 
	 shiftleft(arr,i,SIZE); 
		}
	if (count == 4) exit(0);
	}
my output:
Enter the number of elements: 4
1234
1243
1243
1324
1342
Press any key to continue . . .

the problem are there is a repeated array.

and the second one:regarding to that code

if (count == 4) exit(0);

actually i need to decode :

( count == (n-1)!/2) exit(0);

but cannot.
is it missing something?

[VernonDozier]

Here one of my subroutine

actually i need to decode :

( count == (n-1)!/2) exit(0);

but cannot. is it missing something?

! represents "NOT" in C++, not factorial. You have to write your own factorial function. C++ doesn't provide one.