Thread: Mapping of variables to values (permutation with repetition?)

1. Member
Join Date
Aug 2009
Posts
3
Rep Power
0

Mapping of variables to values (permutation with repetition?)

I would be very grateful to anyone who can give me a basic idea on how to solve the following problem because I am stuck at the moment. (and unfortunately swamped with work and unable to take my time and think about it !!!).

I have a set of variables x1,...,xn. The number of the variables is not fixed.

Each variable has a different domain of distinct values
x1 -> {vx11,...,vx1m} , |dx1|=m
.
.
.
xn -> {vxn1,...,vxnk} , |dxn|=k

The domains do not have equal length.

I want to take all the different assignments of values to
variables.

The number of the possible different assignment is of course |dx1|*|dx2|*...*|dxn|. Basically, it is permutation of distinct objects with repetition (?).

So, if for example I have three values x1, x2, x3
x1 : {1,2}
x2 : {1,2,3}
x3 : {5,6}

The number of possible assignments will be 2*3*2 = 12.

x1 x2 x3
1 1 5
1 1 6
1 2 5
1 2 6
1 3 5
1 3 6
2 1 5
2 1 6
2 2 5
2 2 6
2 3 5
2 3 6

I want to implement in Java a solution that produces all different assignments in the most efficient way possible.

For three variables it would probably take three for loops
but here the number of variables is not predefined. It is given as input every time. Any good ideas? I am sorry if the question is idiotic but I have been working 16 hours a day lately and my brain is stuck at the moment!! Thanks in advance!

2. Hint:

Java Code:
```int[][] values = new int[3][];

values[0] = new int[2];
values[1] = new int[3];
values[2] = new int[2];```

3. Member
Join Date
Aug 2009
Posts
3
Rep Power
0

Thanks

Thanks a lot for your reply! The way you described is how I have stored the domains of the variables. I need to construct a two dimensional array whose number of rows will be equal to the number of variables and the column number will be equal to the number of assignments. In our example:

m[3][12] or generally for x1,....,xn:

m[n][|dx1|*...*|dxn|].

I think I am beginning to see how to do it now. I think it takes four for loops (where a is our initial array with the domains).

Java Code:
```for(int i=0; i<a.length; i++) {
for(int j=0; j<a[i].length; j++) {
for(int k=i+1; k<a.length; k++) {
for(int l=0; l<a[k].length; l++) {

m[i][?] = a[i][j];
}
}
}
}```
I think this might work, with the second dimension of the array going from 0 to |dx1|*...*|dxn|. Maybe with a counter?
Last edited by Fubarable; 08-23-2009 at 05:20 PM. Reason: code tags added

4. Member
Join Date
Aug 2009
Posts
3
Rep Power
0
I haven't tried my idea yet (no time). Can anyone tell me if they agree or disagree with that or if they know of something better? Thanks!

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•