CODEWITHSUNDEEP
javapermutation
user2439222
user2439222

Reputation: 51

Finding the number of ways a word can be permuted in java

I am writing a program in java that will count the number of ways a word can be permuted/rearranged.

For example the word "HAPPY" can be rearranged in 60 ways.

My process is to find the factorial of the length of the word,then dividing it by the multiplication of the factorials of the occurrences of different alphabets present in the word.(using recursion).

Here's my code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
    public static int factorial(int fact)
    {
        if(fact == 0)
            return 1;
        else if(fact == 0)
            return 1;
        return(fact * (factorial(fact - 1)));

    }
    public static void main(String args[]) throws IOException
    {
        String word;
        int result;
        int cases,lengthOfWord;
        int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    cases = Integer.parseInt(br.readLine());
    for(int iteration =1;iteration <= cases; iteration++)
    {
        word = br.readLine();
        lengthOfWord = word.length();
        a = lengthOfWord - word.replace("A", "").length();
        b = lengthOfWord - word.replace("B", "").length();
        c = lengthOfWord - word.replace("C", "").length();
        d = lengthOfWord - word.replace("D", "").length();
        e = lengthOfWord - word.replace("E", "").length();
        f = lengthOfWord - word.replace("F", "").length();
        g = lengthOfWord - word.replace("G", "").length();
        h = lengthOfWord - word.replace("H", "").length();
        i = lengthOfWord - word.replace("I", "").length();
        j = lengthOfWord - word.replace("J", "").length();
        k = lengthOfWord - word.replace("K", "").length();
        l = lengthOfWord - word.replace("L", "").length();
        m = lengthOfWord - word.replace("M", "").length();
        n = lengthOfWord - word.replace("N", "").length();
        o = lengthOfWord - word.replace("O", "").length();
        p = lengthOfWord - word.replace("P", "").length();
        q = lengthOfWord - word.replace("Q", "").length();
        r = lengthOfWord - word.replace("R", "").length();
        s = lengthOfWord - word.replace("S", "").length();
        t = lengthOfWord - word.replace("T", "").length();
        u = lengthOfWord - word.replace("U", "").length();
        v = lengthOfWord - word.replace("V", "").length();
        w = lengthOfWord - word.replace("W", "").length();
        x = lengthOfWord - word.replace("X", "").length();
        y = lengthOfWord - word.replace("Y", "").length();
        z = lengthOfWord - word.replace("Z", "").length();
        result = factorial(lengthOfWord) / (factorial(a)*factorial(b)*factorial(c)*factorial(d)*factorial(e)*factorial(f)*factorial(g)*factorial(h)*factorial(i)*factorial(j)*factorial(k)*factorial(l)*factorial(m)*factorial(n)*factorial(o)*factorial(p)*factorial(q)*factorial(r)*factorial(s)*factorial(t)*factorial(u)*factorial(v)*factorial(w)*factorial(x)*factorial(y)*factorial(z));
        System.out.printf("Data set %d: %d\n",iteration,result);
    }
}
}

But I think it's very lengthy and not efficient.

How can I make this program shorter and more efficient?

I also want to know about other ways of solving this program.

Please assist. Thanks.

Upvotes: 0

Views: 956

Answers (2)

Imre Kerr
Imre Kerr

Reputation: 2428

You can keep the letter counts in an array of length 26. Also, string replacement to check character counts is overly complicated. Just loop through the characters and count them. The letters[word.charAt(j) - 'A'] construct is trickery that makes the count for A appear at index 0, B at index 1 etc. Use a loop to multiply the factorials together. And convert the word to upper case. Finally, always declare variables as close as possible to where they are actually used. (Last one is just general good practice.)

Putting it all together:

public static void main(String args[]) throws IOException
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cases = Integer.parseInt(br.readLine());
    for(int i = 0; i < cases; i++)
    {
        int letters = new int[26];
        String word = br.readLine().toUpperCase();
        int lengthOfWord = word.length();
        for (int j = 0; j < lengthOfWord; j++)
        {
            letters[word.charAt(j) - 'A']++;
        }
        int factorialProduct = 1;
        for (int j = 0; j < letters.length; j++)
        {
            factorialProduct *= factorial(letters[j]);
        }
        int result = factorial(lengthOfWord) / factorialProduct;
        System.out.printf("Data set %d: %d\n",iteration,result);
    }
}

Upvotes: 2

Zong
Zong

Reputation: 6230

You don't use the letters outside the scope of the loop, nor together, so you could have just used a single variable 

String word;
int result;
int cases;
int lengthOfWord;
for(int iteration = 1;iteration <= cases; iteration++) {
    word = br.readLine();
    lengthOfWord = word.length();
    result = factorial(lengthOfWord);
    for (int i = 0; i < letters.length; i++) {
        int divisor = lengthOfWord - word.replace(((char)((int)'A' + i)).toString(), "").length();
        result /= divisor;
    }
System.out.printf("Data set %d: %d\n", iteration, result);

Upvotes: 0

Related Questions