-
July 19th, 2007, 10:35 AM
#1
string permutation
Hi,
Greetings to all,
I am new to this forum , may I ask could if you please give the link to the code for permutation in strings treated as char arrays that is already in this forum . I tried ask.com to reach here for the code. Actually I am unable to develop the correct logic working behind this problem.
I kow that if "joy" is input then output would be
according to index positions :
joy
jyo
ojy
oyj
yoj
yjo
Code:
#include<iostream.h>
#include<conio.h> // these headers need to be modified as per new rules in c++
#include<string.h>
int main()
{
char a[100];
char per[100];
cout<<" word";
cin.get(a,100);
stcpy(per,a);
int l=strlen(per);
for(int x=0;x<l;x++)
for(int y=0;y<l;y++)
{
if(x!=y)
cout<<per[y];
}
cout<<per[x]<<endl;
}
getchar();
return 0;
}
I use turbo C++ for compiling
Help needed in getting hold of different ( index )values of x so that I could swap them up to print 6 combinations instead of 3 .
if you just print per[x]in if loop you will get
oy// 1,2
jy //0,2
jo //0,1
The current output is
oyj
jyo
joy
and my output requires
012
021
102
120
210
201
With lots of hope,
hinduengg
-
July 19th, 2007, 11:02 AM
#2
Re: string permutation
Do you need to create whole permutation thing by yourself? Or maybe you can use std::next_permutation?
Cheers
B+!
'There is no cat' - A. Einstein
Use [code] [/code] tags!
Did YOU share your photo with us at CG Members photo gallery ?
-
July 19th, 2007, 11:10 AM
#3
Re: string permutation
Does Turbo C++ support the standard C++ library ? If
so, there is already a routine which does permutations.
(to get all permutations, the input string must be sorted).
See below for example:
Code:
#include <iostream>
#include <algorithm>
#include <string.h>
int main()
{
char per[100];
strcpy(per,"joy");
int l=strlen(per);
std::sort(per,per+l);
std::cout << per << "\n";
while (std::next_permutation(per,per+l))
{
std::cout << per << "\n";
}
return 0;
}
Output :
joy
jyo
ojy
oyj
yjo
yoj
-
July 19th, 2007, 01:41 PM
#4
Re: string permutation
Thank you for the reply. Actually I need to do this with char arrays only that it is the instruction of my teacher . Do you think my logic or code is flawed . Well thats why the output it produces is not correct. I would be obliged if you would devote some of your precious time to glance through my code and find flaws in it.
I am basically unable to obtain the successive values of x in the if loop.
If i get the individuals I could do swapping b/w the two values like
joy
y=0 so x =1 and x=2 at which if is true so I want to swap these index values .
Should I use break to get hold the values but I am unable to fit the statement in the correct manner.
Code:
char a[100];
char temp;
temp=a[1];
a[1]=a[2];
a[2]=temp;
-
July 19th, 2007, 02:22 PM
#5
Re: string permutation
Originally Posted by hinduengg
Thank you for the reply. Actually I need to do this with char arrays only that it is the instruction of my teacher . Do you think my logic or code is flawed . Well thats why the output it produces is not correct. I would be obliged if you would devote some of your precious time to glance through my code and find flaws in it.
If the output is wrong the code is wrong. Simple as that.
If the purpose of the task is to generate permutations then you shouldn't bother too much about the actual C++ code at first. First you should develop a strategy for generating permutations. This is not an easy task though. Are you sure you haven't been adviced on this?
-
July 19th, 2007, 04:54 PM
#6
Re: string permutation
this may be easier than u think.
1. iterate swap from end to begin
2. iterate swap from begin to end
do this X times which is strlen*Y times, (havent been able to figure out Y)
swap= swap the characters next to eachother
im not sure if this works
-
July 19th, 2007, 07:18 PM
#7
Re: string permutation
Originally Posted by Mitsukai
im not sure if this works
Then why the heck are you posting it?
Do you post just about any crap just to post something?
-
July 20th, 2007, 12:00 AM
#8
Re: string permutation
from GCC STL
Code:
/**
* @brief Permute range into the next "dictionary" ordering.
* @param first Start of range.
* @param last End of range.
* @return False if wrapped to first permutation, true otherwise.
*
* Treats all permutations of the range as a set of "dictionary" sorted
* sequences. Permutes the current sequence into the next one of this set.
* Returns true if there are more sequences to generate. If the sequence
* is the largest of the set, the smallest is generated and false returned.
*/
template<typename _BidirectionalIterator>
bool
next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<
_BidirectionalIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_BidirectionalIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
if (__first == __last)
return false;
_BidirectionalIterator __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;)
{
_BidirectionalIterator __ii = __i;
--__i;
if (*__i < *__ii)
{
_BidirectionalIterator __j = __last;
while (!(*__i < *--__j))
{}
std::iter_swap(__i, __j);
std::reverse(__ii, __last);
return true;
}
if (__i == __first)
{
std::reverse(__first, __last);
return false;
}
}
}
which is something like this
Code:
bool next_permutation(char* first, char* last)
{
char* i = last - 1;
if(first >= i) return false;
while(true)
{
char* ii = i;
if(*--i < *ii)
{
char* j = last;
while(!(*i < *--j));
*i ^= *j;
*j ^= *i;
*i ^= *j;
//std::reverse(ii, last);
return true;
}
if(i == first)
{
//std::reverse(first, last);
return false;
}
}
}
Last edited by Mitsukai; July 20th, 2007 at 12:03 AM.
-
July 20th, 2007, 04:39 AM
#9
Re: string permutation
if you have to implement it yourself, the simplest way is to use recursion.
Code:
void recurse_output_permutations
(
const std::string & remaining,
const std::string & used,
std::ostream & output
)
{
if ( remaining.empty() )
{
output << used << '\n';
return;
}
for( int i=0; i < remaining.size(), ++i ) // ok write it better if you like
{
char ch = remaining[i];
std::string next_remaining( remaining );
next_remaining.erase( i );
std::string next_used( used );
next_used.push_back( char );
recurse_output_permutations( next_remaining, next_used );
}
}
void output_permutations( const std::string & text )
{
recurse_output_permutations( text, "", std::cout );
}
-
July 20th, 2007, 09:25 AM
#10
Re: string permutation
Thank you so much , although the functions used in your codes are very good but my problem is that I need to manually play with indexes of x to get my output.
Those big functions are not required , not to hurt you its just that I have not been taught this until now.
We have to use simple loops and simple C++ string (char array) functions.
Could you throw light on what is recursive programming?
So that when it is taught in class it will be easy for me to grasp.
This question has troubled a lot since 3 weeks and I do not think that I am near to solution. Please pertain to my code please.
Thanking you,
hinduengg
-
July 20th, 2007, 09:49 AM
#11
Re: string permutation
written in C it might look like this:
Code:
#include <stdio.h>
void swap( char * first, char * second )
{
if ( first != second )
{
char temp = *second;
*second = *first;
*first = temp;
}
}
void recurse_output_permutations
(
char * text,
int length,
int partition
)
{
if ( partition == length )
{
puts( text );
return;
}
char * end = text + length;
char * part = text + partition;
for ( char * ch = part; ch != end; ++ch )
{
swap( ch, part );
recurse_output_permutations( text, length, partition + 1 );
swap( ch, part );
}
}
void output_permutations( char * text, int len )
{
recurse_output_permutations( text, len, 0 );
}
int main()
{
char text[] = "stop";
output_permutations( text, 4 );
}
Note this works without making any allocations but if you want to pass in a const char * then your function must make a copy of the string to make it writable.
If you are allowed to use some C++ then you might want to use vector<char> to do this rather than new[] or malloc/strdup (which you would have to use in C).
Output:
stop
stpo
sotp
sopt
spot
spto
tsop
tspo
tosp
tops
tpos
tpso
otsp
otps
ostp
ospt
opst
opts
ptos
ptso
pots
post
psot
psto
Last edited by NMTop40; July 20th, 2007 at 09:58 AM.
-
July 25th, 2007, 09:13 AM
#12
Re: string permutation
THANK YOU NM240 ,your solution is awesome , but please could you throw light on what these lines do in the code:
Code:
char * end = text + length;
char * part = text + partition;
My code has to be in C++ but after you explain in C I would get the logic to implement it in C++.
I would be highly obliged.
Thanking you,
hinduengg
Last edited by hinduengg; July 25th, 2007 at 09:16 AM.
-
July 25th, 2007, 03:55 PM
#13
Re: string permutation
Could you throw light on what is recursive programming?
So that when it is taught in class it will be easy for me to grasp.
May I suggest you to read this article? Its main topic is the merge sort algorithm, but the beginning of the article discusses recursion.
I owe Paul McKenzie a pizza.
I am no expert; but they say I can make concepts easy to understand. That's why newbies questions are mine!!! XD
-
July 26th, 2007, 11:08 AM
#14
Re: string permutation
Thank you Sk# for the nice article and I am sorry to NM top 40 for I misspelled your name. You are one of the gurus of this forums. Sorry.
But my recent question still lingers on . Please try to solve it
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|