Satisfying array constraints

Question

Satisfying array constraints

Given the range 1 to N, where N> = 3. you should take an array of length 2N and place each number (range 1 to N) twice. such that the distance between the two indices of the number is equal to the number. example

N = 3

(3, 1, 2, 1, 3, 2)

The solution I'm thinking about looks like this:

Create each array of permutations of a range of numbers, for example: {1,2,3 |, {3,2,1}, {2,1,3}, etc.

For each permutation array, execute the following functions:

foreach(int number : permutationArray){
    addToResultArray(number);
}

addToResultArray(int toBeAdded){
    for(int i = 0; i < resultArray.length; i++){
        //-1 implies the resultArray is empty at that index
        if(resultArray[i]==-1 && resultArray[i+toBeAdded+1]==-1)
            resultArray[i] = toBeAdded;
    }
}

If the above functions do not throw an out of bounds exception, you have a working solution.

I don't think this solution is very good. Does anyone have something better?

+3

java arrays algorithm constraints

John roberts 18 nov. 14 at 12:18

source to share

1 answer

Xline · Accepted Answer · 2014-11-18T23:31:08+0000

This can be thought of as a limited problem: you have 2*N

variables V={v1,v2,...,v2n}

(representing array indices), each variable has [1,2,..,N]

possible values under constraints:

Each value is assigned exactly two variables.
The distance between variables with the same value is equal to the value itself.

An assignment is a mapping from a set of variables to their possible values. For example, [v1=1,v2=3,v3=5]

is the assignment for v1,v2

and v3

. A given assignment is consistent if it satisfies the constraints. An example of an inconsistent assignment is[v1=3,v2=1,v3=3]

An assignment is complete if its cardinality is equal to the size of the variables (i.e. 2*N

). Otherwise, it is a partial assignment. Clearly our goal is to have one or more complete consistent assignments (aka solution).

So the problem is basically the problem of finding the way back. In particular, we have an ordering by variables. Each time we assign a value to the current variable. If the value makes the current assignment inconsistent, we fall back.

Your approach is actually generate-and-test , which is inefficient. Generating all solutions and accounting for them is a complex problem in general. In most cases, we are looking for one solution.

Here's the fun part: there is a much more efficient way to do this, propagating values and detecting backtracking sooner (see propagation constraints ).

Satisfying array constraints

More articles: