partial permutation using queue

[Mark Nasr]

Hey guys, I have an assignment and part of it is about getting the partial permutation of n numbers using LinkedQueue.
I started on the method but it keeps going on an infinite loop when I set s to an empty string (showed in the code by //here) but when I don't it only returns the variables for example if alphabet contains a,b,c,d it return abcd and that's it. I think it could be solved (or maybe not) when I change the while loop condition but I am not sure what to go with.

public String generateWords() {
		        Queue<String> wordQueue = new LinkedQueue<String>(); 
                        String s = "";
			
			wordQueue.enqueue(s);
			while (s.length() <= getSize()) {
		    	if(!wordQueue.isEmpty()){
		    		
		    		s = wordQueue.dequeue();
		    		
		    		for (int i = 0; i < alphabet.length; i++) {
		        	
		    			s = s + alphabet[i];
		            
		            	wordQueue.enqueue(s);
		            	s = "";  //here
		                
		            }
		        }
		    }
		    while(!wordQueue.isEmpty()){
		    	s =  wordQueue.dequeue() + ";";
		    	
		    }
			return s;
		}

I have another method that will check for repeated variables that I will use when I am done with this method.

[Tushar Goel]

What do you mean by partial permutation? Can you please explain further what do you want to do?

[Campbell Ritchie]

Agree. Please write out the algorithm you intend to use.

[Knute Snortum]

Does getSize() ever return less than zero?

[Mark Nasr]

Sorry for the lack of information. This is what is asked "given an alphabet of N symbols and a size SZ, generates all partial permutations of the alphabet that has the size smaller than or equal SZ."
and an example
"for alphabets {a,b,c,d}
size=3 alphabet size=4
a;b;c;d;ab;ac;ad;ba;bc;bd;ca;cb;cd;da;db;dc;abc;abd;acb;acd;adb;adc;bac;bad;bca;bcd;bda;bdc;cab;cad;cba;cbd;cda;cdb;dab;dac;dba;dbc;dca;dcb;"
From what I unndrstand is that getSize() (which is the size = 3 above) returns the size which is used to generate all the possible letter combinations up to that size number and the alphabet size is the size of the alphabet array which is given.
@Knute size should only return 1 or more

[Campbell Ritchie]

Aha. Have you got an algorithm to create those permutations?

Why are you using a Queue?

[Mark Nasr]

Campbell Ritchie wrote:Aha. Have you got an algorithm to create those permutations?

Why are you using a Queue?

No I have to create all the permutations in this method. I am using a Queue to hold the variables while going over the variables again in the for loop.
I should be using something similar to this method.

//This method looks for the best path in a Labyrinth game
public boolean solve(int solutionSize) {

    findStartPos();

    LinkedQueue q = new LinkedQueue();
    String newpath = "";
    q.enqueue(newpath);
    boolean solved = false;
    boolean unsolvable = false;

    while (!solved && !unsolvable) {
        if (q.isEmpty() || q.isFull())
            unsolvable = true;
        else {
            String path = (String) q.dequeue();
            for (int m=0; (m < MOVES.length) &&
                          (! solved) && 
                          (! unsolvable) ; m++) {
                newpath = path + MOVES[m];
                if (checkPath(newpath))
                    if (reachesGoal(newpath))
                        solved = true;
                    else
                        if (q.isFull())
                            unsolvable = true;
                        else if (newpath.length() 
                                  <= solutionSize)
                            q.enqueue(newpath);
            }
        }
    }
    if (solved)
        trace(newpath);
    return solved;

[Mark Nasr]

My method should do something similar to this

[Campbell Ritchie]

And do you understand what the diagram means?

[Henry Wong]

Mark Nasr wrote:My method should do something similar to this

Why don't you just print out each iteration to see exactly what is happening?? If you do, you will likely see something like this...

new queue               []
enqueue("")             [""]
s = "" = dequeue()      []
enqueue(L)              [L]
enqueue(R)              [L,R]
enqueue(U)              [L,R,U]
enqueue(D)              [L,R,U,D]
s = "L" = dequeue()     [R,U,D]
enqueue(LL)             [R,U,D,LL]
enqueue(R)              [R,U,D,LL,R]
enqueue(U)              [R,U,D,LL,R,U]
enqueue(D)              [R,U,D,LL,R,U,D]
s = "R" = dequeue()     [U,D,LL,R,U,D]
enqueue(RL)             [U,D,LL,R,U,D,RL]
enqueue(R)              [U,D,LL,R,U,D,RL,R,U,D]
enqueue(U)              [U,D,LL,R,U,D,RL,R,U,D]
enqueue(D)              [U,D,LL,R,U,D,RL,R,U,D]

Etc. etc. etc. (endless loop)

Henry

[Mark Nasr]

I solved the problem thanks guys

[Knute Snortum]

How did you do it? Would you like to post what you did?

[Mark Nasr]

This is the solution I found

public String generate() {
		Queue<String> wordQueue = new LinkedQueue<String>(); 
                String s = "";
			
			wordQueue.enqueue(s);
			while (s.length() <= getSize()) {
		    	if(!wordQueue.isEmpty()){
		    		
		    		s = wordQueue.dequeue();
		    		
		    		for (int i = 0; i < alphabet.length; i++) {
		    			
		    			 wordQueue.enqueue(s + alphabet[i]);
		            
		            }
		        }
		    }
		    while(!wordQueue.isEmpty()){
		    	String temp = checkDup(wordQueue.dequeue());  //checkDup(String) method will check if any of the variables are repeated
		    	if(temp == ""){		    		
		    	}
		    	else{
		    		s = s + temp + ";";
		    	}		    
		    }
		    return s;		
		}

[Knute Snortum]

Good job.

This:

if(temp == ""){                 
                }
                else{
                    s = s + temp + ";";
                }   

can be this:

if (!temp.isEmpty()) {
  s += temp + ";";
}

[Campbell Ritchie]

And of course that way you are not using the == operator.