java how to avoid duplicate in recursion

Question

i'm trying to search synonym(which i declare as 'synset') recursively. Unfortunately, there are duplicate of synonym. For example: when i search the word student, the output will be like this:

Search word: student

Synset 0: pupil
  Synset 0: student
    Synset 0: pupil
    .
    .
    .
  Synset 1: educatee
  Synset 2: schoolchild
Synset 1: educatee
Synset 2: scholar
Synset 3: bookman

I want to store all the output into database and I do not need the duplicate output.This is part of my code that consist recursive function. Hope anyone can help me..Thanks

public String printSynset(String word)
    {
        //call wordnet library

        RiWordnet wordnet = new RiWordnet();
        //call stemmer method
        PorterStemmer s = new PorterStemmer();

    Vector<String> synsetVec = new Vector<String>();
    String[] synset = wordnet.getAllSynsets(word, "n");

    for (int k=0; k<synset.length; k++)
    {
        synsetVec.add(synset[k]);

        if (!synsetVec.isEmpty())
        {
            for (int j = 0; j < synsetVec.size();) 
            {   
                GUIsynonymTA.append("\n");
                GUIsynonymTA.append("   No." + j + ": " + (s.Stem(synsetVec.get(j))));
                GUIsynonymTA.append("\n");

                return printSynset(synsetVec.get(j));
            }
        }

        else if (synsetVec.isEmpty())
            return word;

    }
    return word;
}//end printSynset()

@Divyesh I don't think this question is a duplicate of the one you linked to. — Vivin Paliath
– Vivin Paliath, Commented Sep 30, 2011 at 14:12
On a side note, there is no point in doing an if (!sysnsetVec.isEmpty()) and then an else if (sysncVec.isEmpty()). If the if returns false you can just do an else. — John B
– John B, Commented Sep 30, 2011 at 14:18

Fred Foo · Accepted Answer · 2011-10-02 08:49:28Z

7

You should maintain a Set of the items you've already seen. Every time you hit an item, first check whether it's been seen before; if it is, stop the recursion; if it's not, add it to the set and proceed.

The result is the classic depth-first search for general graphs, which you can find in any algorithms textbook or in Russell & Norvig chapter 3. Pseudocode:

Set<Node> printSynset(Node root) {
    HashSet<Node> closed;
    printDFS(root, closed);
}

// recursive graph dfs
void printDFS(Node n, Set<Node> closed) {
    if (!closed.contains(n)) {
        print(n.item);
        closed.add(n);
        for (Node s : n.neighbors())
            printDFS(n, closed);
    }
}

Note that when printDFS returns to printSynset, it will have filled closed with all nodes it has visited, so you could also choose to return that Set<Node> and loop over it in printSynset, instead of doing the printing in printDFS. That would leave you with a general, re-usable DFS routine.

edited Oct 2, 2011 at 8:49

answered Sep 30, 2011 at 14:12

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

syakirah ibrahim Over a year ago

Thanks @larsmans. Actually this is what i'm trying to do. Using depth-first search to get the results. Just because i do not know how to implement it here, i'm tring to use recursion.

Thorbjørn Ravn Andersen Over a year ago

recursion is fine for depth-first search. You just need to be 100% sure that your recursion will not happen for every step because then you have infinite looping which for recursion results in stackoverflow

Fred Foo Over a year ago

@syakirahibrahim: added pseudocode for a recursive DFS printing routine.

AlleyOOP Over a year ago

Does this mean that the Set is a global variable(in Java) ? I can't imagine how a recursive function can pass the Set through the recursion chain by value and maintain consistency.

John B · Accepted Answer · 2011-09-30 14:12:28Z

4

Use a Set to store the previously found matches. If the word is in the Set don't output it again.

Set

Maintain the Set as a class level field so that all the recursions of the method have access to the Set. If Set.add(word) returns false you know that the word was already in the Set.

answered Sep 30, 2011 at 14:12

John B

33.1k8 gold badges80 silver badges100 bronze badges

Collectives™ on Stack Overflow

java how to avoid duplicate in recursion

2 Answers 2

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related