Multi-dimensional space algorithm

Question

I have been trying to design an algorithm that could subtract chunks of N dimensional space from another N dimensional space.

The napkin draft at the bottom is showing bit of math and visuals using 2 dimensional space for the sake of simplicity.

The business problem: Imagine having a 30 sets of data (in this case meaning 30 dimensional space) of all possible combinations. The Cartesian product would display me all possible combinations however the problem is that I need to reverse it. Make it so when I get say 15 instances of 30 dimensional data I could just chunk my way through the initial 30 dimensional space and see if anything left uncovered.

First problem is that I have not found any 3rd party JAVA libraries to deal with this - maybe I am not using correct keywords, my education was not in English language.

Now second problem is that I am trying to work this out in java. As you can see there is a simplified UML diagram next to the XY coordinate space representing the structure. For data storing I want to use Map<Object, Set<String>> (Object is the dimension and Set are its values) cause I do not want to limit what key should represent a dimension and I want my dimensions to hold String values as they already have hashCode and equals methods overridden.

So I've been working on subtract algorithm for SimpleSpace:

    public AbstractSpace subtract(AbstractSpace abstractSpace) {
        //Some checks
                if (!(abstractSpace instanceof SimpleSpace)) {
                    return null;
                }
                if (getDimensions().size() != abstractSpace.getDimensions().size()) {
                    return null;
                }
                if (!getDimensions().equals(abstractSpace.getDimensions())) {
                    return null;
                }

                SimpleSpace spaceToRemove = (SimpleSpace) abstractSpace;
                final Map> template = Maps.newHashMap();
                final Set prevDimension = Sets.newHashSet();
                final List result = Lists.newArrayList();
                //getDimensions() just retrieves the SimpleSpace Map.keySet()
                for (Object dimension : getDimensions()) {
                //copy method makes a deep copy of current simpleSpace map as I do not want to change state of SimpleSPace instance
                    SimpleSpace editSpace = copy();
                    editSpace.remove(dimension, spaceToRemove.getValues(dimension));
                    //This bit over here is implementation of my poor math understandment
                    for (Object prevKey : prevDimension) {
                        editSpace.getValues(prevKey).removeAll(template.get(prevKey));
                    }
                    prevDimension.add(dimension);
                    template.put(dimension, editSpace.getValues(dimension));
                    result.add(editSpace);
                }
                 //I remove all simpleSpaces which have a dimension with empty set (this is not efficient but this is the first iteration) 
                Iterables.removeIf(result, new Predicate() {
                    @Override
                    public boolean apply(SimpleSpace input) {
                        return input.isEmpty();
                    }
                });

                return new CompositeSpace(result);
            }

While this works I seem to work with 2 dimensional example I don't fully understand how to test it with N dimensional spaces.

Should I (add) all of the composite spaces back together to try and see if the N dimensional space broken apart can be put back together ? By the way maybe someone could suggest a more efficient algorithm ?

If there is any piece of information missing please let me know.

Thank you.

Answer 1

This is really a constraint programming problem in disguise. Each dimension corresponds to a variable and its possible values. Each SimpleSpace corresponds to a constraint requesting that at least one of the variables have a value outside of the specified subset. The uncovered points and the feasible solutions are in one-to-one correspondence. Even basic constraint programming libraries will be a considerable improvement on brute force.