Number of permutations

[adina0822]

Please help me to solve this:

We are considering a word C containing only lowercase.
An anagram of the word C is a word formed by the letters of C in another order eventually.
E.g.
'armata' is an anagram of the word 'tamara'
but 'maree' is not an anagram of the word 'amare'
A word is an angram of itself.


Determine the number of different anagrams that a word has. Because this number may be very high, there will be posted its decomposition into prime numbers

The input file anagrame.in contains the word C.

The output file anagrame.out will contain the decomposition into prime numbers of the number of anagrams of the word C. On each line there will be a prime factor followed by one space and then its multiplicity(power). The factors will be written in ascending order.


0 < the length of the word <= 1000

e.g
anagrame.in
amar

anagrame.out
2 2
3 1

anagrame.in
informatician

anagrame.out
2 7
3 4
5 2
7 1
11 1
13 1

[MiiNiPaa]

http://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets

[adina0822]

Thanks. I know the formula. My problem is the efficiency.

using namespace std;
#include <fstream>
#include <string.h>
ifstream f ("anagrame.in");
ofstream g ("anagrame.out");




int main()
{
char c[1005],*p;
int i,x,i2,d,nr,j,v[1005]={0};

f.getline (c,1005);

x=strlen (c);

for (i=2; i<=x; i++)
{
i2=i;
while (i2%2==0)
{
i2/=2;
v[2]++;
}

d=3;
while (i2!=1)
{
while (i2%d==0)
{
i2=i2/d;
v[d]++;
}
d+=2;
}

}

for (i=0; i<strlen(c); i++)
{
nr=0;
p=strchr (c+i+1,c[i]);
while (p)
{
nr++;
strcpy (p,p+1);
p=strchr (c+i+1,c[i]);

}
if (nr!=0) nr=nr+1;

for (j=2; j<=nr; j++)
{
i2=j;
while (i2%2==0)
{
i2/=2;
v[2]--;
}

d=3;
while (i2!=1)
{
while (i2%d==0)
{
i2=i2/d;
v[d]--;
}
}
d+=2;
}
}

for (i=2; i<=x; i++) if (v[i]) g<<i<<" "<<v[i]<<'\n';


return 0;
}

[prestokeys]

#include <iostream>
#include <algorithm>
#include <set>
#include <string>

std::set<std::string> numAnagrams (std::string& word) {
	std::set<std::string> anagrams;
	std::sort(word.begin(), word.end());
	do anagrams.emplace(word);
  	while (std::next_permutation(word.begin(), word.end()));
  	return anagrams;
}


int main() {
	std::string word = "hello",  originalWord = word;
	std::set<std::string> anagrams = numAnagrams(word);
//	for (const std::string& x : anagrams) std::cout << x << std::endl; // In case you wanted to see them all.
	std::cout << "\nNumber of anagrams of '" << originalWord << "' is " << anagrams.size() << ".\n";
}

Output:
Number of anagrams of 'hello' is 60.

The prime factorization and fstream handling is up to you now.

If you are not allowed to use the algorithm library, then keep swapping the letters of the word, placing each new arrangement into a set (so that duplicates are ignored), until you've returned to the original word, in which case stop.

[MiiNiPaa]

@prestokeys, this code is especially amusing after warning in OP post about large numbers and efficiency questions.
set for all permutations of informatician would be about 4GB in size.

@OP:
1) find factorisation of numerator of multiset permutation formula and store results in a vector. Sort it . Example:

5! = 1 * 2 * 3 * 4 *  5 = (2) * (3) * (2 * 2) * 5;
so vector will be:
{2, 2, 2, 3, 5}

2) find factorisation of denominator and store results in another vector. Sort it:

for 'Hello'
1! * 1! * 1! * 2! = 2
resulting vector is
{ 2 }

Then apply set_difference algorithm:
http://en.cppreference.com/w/cpp/algorithm/set_difference

result is:
[output]2 2
3 1
5 1

{2, 2, 3, 5}. [/output]Then count each distinct element and

[prestokeys]

So the OP's question is just about the math of prime factorization and not about the anagrams?

[MiiNiPaa]

His problem is about efficient implementation of calculation of number of different anagrams which is reduced to efficient implementation of abstract math alghorithm.

[adina0822]

Thank you!