## Check if an number is an permutation

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Check if an number is an permutation

Hi! I'm using this code to see if a number is an permutation of an vector. But it doesn't work as I wish it would. Also, how can I make the code shorter and more efficient?

[syntax="cpp"]bool isPermutation(int tal, vector <int> vektor ){
vector <int> temp = tillVektor(tal);
int * vektorn = new int[temp.size()];
std::copy(temp.begin(),temp.end(),vektorn);
int * vektor1 = new int[vektor.size()];
std::copy(vektor.begin(),vektor.end(),vektor1);
int * vektor2 = new int[vektor.size()];
std::copy(vektor.begin(),vektor.end(),vektor2);

while (next_permutation(vektor2, vektor2 + vektor.size())){
bool sant = true;
for (int i = 0; i < temp.size(); i++)
if (vektor2[i] != vektorn[i])
sant = false;
if (sant) return true;
}

while (prev_permutation(vektor1, vektor1 + vektor.size())){
bool sant = true;
for (int i = 0; i < temp.size(); i++)
if (vektor1[i] != vektorn[i])
sant = false;
if (sant) return true;
}
return false;
}[/syntax]

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

How can a number be a permutation of a vector? A permutation of a vector is another vector.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

I assume you convert the int to vector with each element containing 1 digit of the number , am i right ?
That should be easy with O(n^2) algorithm ! .

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

Here's some food for thought: for one vector to be a permutation of another, they only have to have the same size and the same elements (but in any order).

If you think about those two criteria I'm sure you can come up with a better algorithm.

Bugdude
Moderator

Posts: 2480
Joined: Sun Aug 29, 2004 1:58 am
Location: Living in sin

Blueteeth: Yes the function tillVektor(int) converts int to vector. I have no clue what the O(n^2) algorithm is.

However I solved it.

[syntax="cpp"]bool isPermutation(int tal, vector <int> vektor ){
vector <int> temp = tillVektor(tal);
if (temp.size() != vektor.size())
return false;
sort(temp.begin(), temp.end());
sort(vektor.begin(), vektor.end());
if (vektor == temp)
return true;
return false;

}[/syntax]

I guess that is a better algorithm

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

<------- = a noob

...could i get an explination of all this?
What Could Go Wrong?
The Insomniacs Dream

Posts: 230
Joined: Mon Dec 13, 2004 8:41 pm
Location: CHEESE!!!

That's far better , it's O(nlgn) .
As for the O(-) thing , it's called Big-Oh Notation , it's a way for describing the complexity of an algorithm .

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt