CODEWITHSUNDEEP
java
Daniel S
Daniel S

Reputation: 49

Iterate through TreeSet without repeating solutions

I am making combinations of 3 different values that give a requested sum, in this case the requested sum is 0.
I can't find a way to iterate through a TreeSet with 2 for loops in order to receive a set of 3 numbers without repeating that solution. The third number I would like to obtain by using the contains method of the TreeSet.

This is my code so far, it gives good solutions but it repeats them.

import java.util.*;

public class Tree
{
    public static void main(String[] args)
    {
        TreeSet<Integer> ts = new TreeSet<>();
        int array[] = {-5, 1, -4, 6, 2, 3, 9, 5};

        int sumSearching = 0;
        int valueSearching;

        for(int i = 0; i < array.length; i++)
            ts.add(array[i]);

        for(Integer i: ts)
        {
            for(Integer j : ts)
            {
                if(i != j)
                {
                    valueSearching = sumSearching - (i + j);
                    if(valueSearching != i && valueSearching != j)
                        if(ts.contains(valueSearching))
                            System.out.println("Solution: "
                                + i + ", " + j + ", " + valueSearching);
                }
            }
        }
    }
}

Thanks for any kind of help!

Upvotes: 1

Views: 64

Answers (3)

Joop Eggen
Joop Eggen

Reputation: 109577

Go for j > i, removing one symmetry.

This does not exclude doubles on {i, j, valueSearching} as negative numbers are involved. So one needs to maintain all solutions.

    Set<Set<Integer>> solutions = new HashSet<>();
    for (int i: ts)
    {
        for (int j : ts.tailSet(i, false))
        {
            valueSearching = sumSearching - (i + j);
            if (valueSearching != i && valueSearching != j)
                if (ts.contains(valueSearching)) {
                    Set<Integer> solution = new TreeSet<>();
                    Collections.addAll(solution, i, j, valueSearching);
                    if (solutions.add(solution)) {
                        System.out.println("Solution: "
                                + i + ", " + j + ", " + valueSearching);
                    }
                }
        }
    }

Also note: i != j for Integers should better be i.intValue() != j.intValue() as only in the range -128 .. 127 the object for a number is unique.

Here simply the int primitive type is used, which is more appropriate. Also Set.tailSet(value, exclusive) gives the set after the value. Using an Iterator probably would be more efficient.

Upvotes: 1

Elyor Murodov
Elyor Murodov

Reputation: 1028

To exclude repeating solutions, it's enough to include only those triples which are in ascending order.

So, try changing this line:

if (valueSearching != i && valueSearching != j)

to:

if (i < j && j < valueSearching)

Upvotes: 0

Michael
Michael

Reputation: 44170

Implement a reversable pair class:

class ReversablePair<T>
{
    private final T first;
    private final T second;

    ReversablePair(final T first, final T second)
    {
        this.first = first;
        this.second = second;
    }

    // Some getters...

    @Override
    public boolean equals(final Object o)
    {
        if (o == null) return false;
        if (!(o instanceof ReversablePair)) return false;

        final ReversablePair that = (ReversablePair) o;

        return (this.first.equals(that.first) && this.second.equals(that.second))
            || (this.first.equals(that.second) && this.second.equals(that.first));
    }

    @Override
    public int hashCode()
    {
        return first.hashCode() + second.hashCode();
    }
}

Then maintain a set of previous solutions:

Set<ReversablePair<Integer>> previousSolutions = new HashSet();

And check the set before printing:

if (! previousSolutions.contains(new ReversablePair<>(i, j))
{
    // whatever
}

Upvotes: 0

Related Questions