nth permutation step based on character set

May 13, 2011 at 06:27:41
Specs: Windows 7XP, 4gb
Hi! I would like to write a program that determines a string's position based on a character set. Example:
character set: abc
string length: 3
input string: aaa

answer: 1

character set: abc
string length: 3
input string: aba

answer: 4


1. aaa
2. aab
3. aac
4. aba
5. abb
.
..
...

i would like to write this myself, just please give me a push in the right direction?


See More: nth permutation step based on character set

Report •


#1
May 13, 2011 at 12:39:18
So what are you looking for here? Basic logic? You're basically converting base-n to base-10, but with abstract symbols defined at runtime. It'd be possible to figure things out in some type of loop, but it'd be easier to just use the conversion formula (linked above).

The hardest part is matching the symbol to its value. For that, you could use a vector/array and make heavy use of std::find(), or you could use the std::map (and make use of its std::map::find()).

How To Ask Questions The Smart Way


Report •

#2
May 19, 2011 at 04:58:15
i already figured out how to search for the character position in the array:

int getChsetPos(char c, char *str){
int i, n=-2;
for(i=0; i<strlen(str); i++){
if(str[i]==c)
n=i;
}
return n+1;
}

what i want to know is if there is an easy way to find the string's position based on the permutation, given a string length and a character set. Example: string length of 3, character set of abc. User would input aaa, output would be 1 because aaa would be the first in the permutation, aab second, aac third, aba fourth, abb fifth and so on.


Report •

#3
May 19, 2011 at 07:40:41
Alright, time for a perspective shift.

character set: 0123456789
string length: 3
input string: 010

What's the permutation?

How To Ask Questions The Smart Way


Report •

Related Solutions

#4
May 19, 2011 at 19:18:05
11th.

1. 000
2. 001
3. 002
4. 003
5. 004
6. 005
7. 006
8. 007
9. 008
10. 009
11. 010


Report •

#5
May 22, 2011 at 07:22:03
Good. Now do 829.

As much as I would love to see you count from 0 to 829, in the interest of expediency, I'm just going to move onto the next step.

What you're looking for is the value of the "number," plus 1 (since you start counting at 0, and not 1).

829 can be written as (800 + 20 + 9).
Since we're dealing with base 10 (instead of, say, 3), we can say (800 + 20 + 9) = ((8 * 10^2) + (2 * 10^1) + 9).
If this was base 16, we could say (800 + 20 + 9) = ((8 * 16^2) + (2 * 16^1) + 9).

So let's move this from a formula, and put it into words: Take your number; shift it to the left by multiplying it by the base; and add the new digit. Once you're out of digits, you have your number. Add one, and you're done.

How To Ask Questions The Smart Way


Report •

#6
June 1, 2011 at 08:35:34
tnx Master Razor! i finished the program:

#include<stdio.h>
#include<string.h>
#include<math.h>

int getChsetPos(char c, char *str){
int i, n=-2; //n is negative so that it will return a negative value if character is not in character set.
for(i=0; i<strlen(str); i++)
if(str[i]==c)
n=i;
return n;
}

main(){
int i;
char string[100], chset[100];
double prod=0;

printf("Input string: ");
gets(string);//get string

printf("Input character set: ");
gets(chset);//get character set

strrev(string);//reverse string for ease of counting and to simplify the for loop

for(i=0; i<strlen(tString); i++)
prod+=(getChsetPos(tString[i], chset)*pow(strlen(chset), i));

if(prod<1){ //user made a mistake in input string or character set
printf("Error! Characters in the input string are not found in the character set.\n");
system("Pause");
exit(1);
}
else
prod++; //add 1 because counting started at 0
printf("%0.lf\n", prod);
system("PAUSE");
}

but how do i do it in reverse? if i follow the logic:

4582 % 10 = 2 (Digit# 1)

4582 / 10 = 458
458 % 10 = 8 (Digit# 2)

458 / 10 = 45
45 % 10 = 5 (Digit# 3)

45 / 10 = 4
4 % 10 = 4 (Digit# 4)

assuming that the character set is abcd which has a string length of 4. should i still follow base ten? or should it be in base 4?


Report •


Ask Question