CODEWITHSUNDEEP
javastringpermutationcombinatorics
dasdasd
dasdasd

Reputation: 39

Generating all words of length N from a given alphabet in Java

The cleanest way to generate all N - length words, with characters from a given alphabet , such that they must have in them a given character c.

If the length is 2, for an alphabet with this characters {a,b} , and the character is 'b' it should return a list like this:

ab , ba , bb

So far I am thinking of using nested loops, but it's not clean, or using similar methods to permutation , to generate them all by increment the least significant bit and wrapping around when reaching last character from alphabet.

EDIT:

    ArrayList <String> data = new ArrayList <String>();
    int iterations = (int) Math.pow(alfabet.length, N);

    int  pos [] = new int [N];
    pos[N-1] = -1;
    for (int i = 0 ; i < iterations;i++)
    {
        pos[N-1]++;
        for (int j = N-1; j >= 0;j--)
        {
            if (pos[j] == alfabet.length) 
            {
                pos[j] = 0;
                pos[j-1] ++;
            }
            else break;
        }
        String word = "";
        for (int j = 0 ; j < N; j++ )
        {
            word += alfabet[pos[j]];
        }
        int val = 0;
        for (int j = 0 ; j < lst.length; j++)
        {
            if (word.contains(lst[j] + "")) val++;
        }
        if (val == lst.length) data.add(word);

    }
    return data;

This is the function i built, i made the alphabet static, for easier access through the code, and because i wont change it. Improved on it a bit, and made it so that it doesnt check just a character, but a certain array of characters. Would like a review of clarity, complexity or some things that i might have looked over.

Upvotes: 1

Views: 1165

Answers (1)

Paulo Mattos
Paulo Mattos

Reputation: 19339

Since you didn't provide any Java code, I won't either ;) I don't want to spoil your fun...

A short, somewhat fast, non-recursive solution in pseudocode (aka, Swift) to get you going:

let alphabet = ["a", "b", "c"]
let requiredChar = 2

func printAllWords() {
    var word = [0, 0]
    for _ in 0 ..< pow(alphabet.count, word.count) {
        if word.contains(requiredChar) { print(word) }
        for char in 0 ..< word.count {
            word[char] = (word[char] + 1) % alphabet.count
            if word[char] != 0 { break } // overflow
        }
    }
}

outputs the desired words:

ca
cb
ac
bc
cc

This should run in O(n.zⁿ) time complexity, where:

  • n is the word length;
  • and z the alphabet length.

To play around with this code, try this Swift sandbox.

Getting a working Java version out of this should be straightforward. A Kotlin version should be even easier... ;)

Upvotes: 3

Related Questions