Challanging algorithm problem
Hi all,
I'll try to describe the problem with my poor english.
I have N sets of consecutive values, for example:
Set 1 = { 1,2,3,4,5 }
Set 2 = { 4,5,6 }
Set 3 = { 3,4,5,6,7,8,9 }
Set 4 = { 0,1,2,3 }
I need to construct all the possible sets of N values, each of which is taken from each of the N sets, for example:
{ 1,4,3,0 } { 1,4,3,1 } { 1,4,3,2 } { 1,4,3,3 }
{ 1,4,4,0 } { 1,4,4,1 } { 1,4,4,2 ] { 1,4,4,3 }
and so on...
There would be 5x3x7x4=420 possible sets, but:
two sets are equivalent if they contain the same values (as definition of SET), for example:
{ 3,4,4,0 } is equivalent to { 4,4,3,0 } and one of these can be "discarded"
What's the best algorithm to build all the possible sets (without duplicate sets)?
The average case will be N=20 and set size of 10.
Challenging huh?
Antonio :)
[912 byte] By [
biantoa] at [2007-9-28 18:34:52]
I'm concerned about performance and memory usage.
If you have 20 sets of 10 values each you need to have a loop of 7,766,279,631,452,241,920 (10^20) iterations when the actual final number of sets will be much lower.
A small improvement can be obtained by using steps like this:
1. I get the first set and build a set for each element
2. To each one-value set I add the second set values
3. Discard the duplicated two-values sets
4. Add the third set values
5. Discard the 3-values duplicate sets
and so on...
For example:
{1,2,3}
{2,3}
{4,5}
1. {1} {2} {3}
2. {12} {13} {22} {23} {32} {33}
3. eliminate the set {32}
4. {124} {125} {134} {135} {224} {225} {234} {235} {334} {335}
5. nothing to do in this case
There must be a better algorithm to solve this problem in less then O(x^N) :-\
Antonio.
( the symbol ^ means power )
> There must be a better algorithm to solve this problem in less then O(x^N)No, because the output is of size O(x^N).
Correction: the output is of size THETA(x^N) worst-case (and possibly best-case).
Yes, you are right, the output can may contain x^N sets but I still think there is a smarter algorithm to solve the problem, instead of merely obtain the set-product between all the sequences of numbers.
I say so because in my real application the values in one set are very close to the number of the next set, and this produces a lot of equivalent sets. Think about this situation, similar to my average case:
{1,2,3,4,5,6,7,8,9,10}
{3,4,5,6,7,8,9}
{4,5,6,7,8,9,10}
{4,5,6,7,8,9,10,11,12}
Antonio :)
I do not think the following is a very neat code, but results are calculated at least.
Order of numbers taken from sets is not preserved but duplication is avoided.
final public class Challenge0{
static int N=9,p=4, num=0;
static int[][] check = new int[5*3*7*4][10];
static int index;
private static void print(MyList L){
int tmp=0;
while(L!=null){
tmp = L.getValue();
check[index][tmp]++;
L=L.getNext();
}
boolean duplication_flag =false;
Label:for(int m=0;m<index;m++){
for(int h=0;h<10;h++){
if(check[index][h]==check[m][h]) duplication_flag=true;
else {
duplication_flag=false;
break;
}//end of if-else
}//end of for
if(duplication_flag) break Label;
}//end of Label: for
int[] copy = new int[10];
if(!duplication_flag){
System.arraycopy(check[index],0,copy,0,10);
for(int k=0;k<10;k++){
while(copy[k]>0){
System.out.print(k);
copy[k]--;
}
}
System.out.println();
num++;
}//end of if
index++;
}
public static void main(String[] args){
MyList[] L=new MyList[p];
for(int i=1;i<=5;i++){//(step1)
L[0] = new MyList(i,null);
for(int k=4;k<=6;k++){ //(step2)
if(L[0]!=null){
L[1] = L[0].addNext(k);
for(int q=3;q<=9;q++){//(step3)
if(L[1]!=null){
L[2] = L[1].addNext(q);
for(int w=0;w<=3;w++){ //(step4)
if(L[2]!=null){
L[3]=L[2].addNext(w);
//........... printing .........//
if(L[p-1]!=null) Challenge0.print(L[p-1]);
// .........end of printing........//
}//end of if
}//end of for
}//end of if
} //end of for
}//end of if
}//end of for
}//end of for
System.out.println();
System.out.print("total number of results are: ");
System.out.println(num);// total number of outcomes
} //end of main
} //end of class
class MyList{
private int n, length;
MyList next;
public MyList(int n, MyList list){//constructor
if(list==null) this.length=1;
else this.length=list.length + 1;
this.n=n;
this.next = list;
}
public int size(){
return this.length;
}
public MyList addNext(int m){
return new MyList(m, this);
}
MyList getNext(){
return this.next;
}
public int getValue(){
return this.n;
}
}
Yes fsato4,
this code prints out the expected result, the algorithm is simple and works well. I'm going to give you some dukes for that.
However, it generates all the possible combinations and, only in the printing phase, it checks for duplicates.
I cannot affort to store all the combination in memory :( They can be a very high number (avarage 10^20).
The algorithm you wrote is only suitable when the number of input set is four. What happens if the number of set changes to every execution?
Antonio :)
Here's an idea. Since the order of the numbers is inconsequential, you can store your sets in a different form that allows you to avoid computing the same combinations. Essentially, take each number and count the max number of times it can appear. For your example that would be:
1: 2
2: 2
3: 3
4: 3
5: 3
6: 2
7: 1
8: 1
9: 1
Then, start by finding every possible 4 number combinations like so:
1,1,2,2 1,1,2,3 1,1,2,4 1,1,2,5 1,1,2,6 1,1,2,7 1,1,2,8 1,1,2,9
1,1,3,3 1,1,3,4 1,1,3,5 1,1,3,6 1,1,3,7 1,1,3,8 1,1,3,9
1,1,4,4 1,1,4,5 1,1,4,6 1,1,4,7 1,1,4,8 1,1,4,9
1,1,5,5 1,1,5,6 1,1,5,7 1,1,5,8 1,1,5,9
1,1,6,6 1,1,6,7 1,1,6,8 1,1,6,9
1,1,7,8 1,1,7,9
1,1,8,9
1,2,2,3 1,2,2,4 1,2,2,5 1,2,2,6 1,2,2,7 1,2,2,8 1,2,2,9
1,2,3,3 1,2,3,4 1,2,3,5 1,2,3,6 1,2,3,7 1,2,3,8 1,2,3,9
1,2,4,4 1,2,4,5 1,2,4,6 1,2,4,7 1,2,4,8 1,2,4,9
1,2,5,5 1,2,5,6 1,2,5,7 1,2,5,8 1,2,5,9
1,2,6,6 1,2,6,7 1,2,6,8 1,2,6,9
1,2,7,8 1,2,7,9
1,2,8,9
etc.
The above can be done with a generic recursive method. Just reply if you aren't sure how.
This is a great algorithm, but I think it has a lack. I hope I am wrong.
How do you estabilish the MINIMUM occurrance of a value?
The algorithm set the MAXIMUM occurance of each value but some situation requires one value to be always present in the result sets.
An example can maybe explain better what I mean:
{1,2}
{6,7}
{1,2,3,4}
we have this occurance matrix:
1:2 - 2:2 - 3:1 - 4:1 - 6:1 - 7:1
With the algorithm you suggested we have {346}{347}{467} in the result while these sets are not valid sets because they don't get any value from the first set.
Antonio.
> With the algorithm you suggested we have
> {346}{347}{467} in the result while these sets are not
> valid sets because they don't get any value from the
> first set.
You are absolutely right. I'm going to think about it and see if there is a way to fix it.
You could instead transpose the sets like so:
input: {1,2} {6,7} {1,2,3,4}
trans: 1: {1,3}
2: {1,3}
3: {3}
4: {3}
6: {2}
7: {2}
The length of the transposed list is the same as the number of times a variable is allowed.
The simple solution is to do like I said before but after each computation make sure that every set is represented i.e.
1,1,2 [fail]
1,1,3 [fail]
1,1,4 [fail]
1,1,6 [pass]
1,1,7 [pass]
1,2,2 [fail]
1,2,3 [fail]
1,2,4 [fail]
1,2,6 [pass]
1,2,7 [pass]
So now it works. I'll go out on a limb and guess this is better than the first algorithm because we don't have to sort the entire result and check for duplicates but we are still doing more computation than is neccesary. It would be better if we could eliminate creating the invalid combos altogether.
I have actual work to do right now but I'm going to keep thinking about it. Maybe you could start coding this. I'm cautiously optomistic we can tweak this to be even better.
I've got it. I'm not sure it's the most efficient algo ever but let me solve this bug at work and I'll get back to you.
Sure, I'm working too.Sorry for late replies :-)Antonio.
Still not clear how you reject {1, 6, 7}, unless you have an expensive operation assigning each number to its set of origin.
The obvious way to solve the original problem when you only have two sets to start with is for (int x0 = a0; x0 <= b0; x0++)
for (int x1 = a1; x1 < b1; x1++)
if (x0 <= x1 || // this imposition of ordering removes duplicates
x1 < a0 ||// this allows x1 < x0 if it won't cause a duplicate
x0 > b1)// as does this
output(x0, x1);
I'm not sure whether this can be generalised to n sets.
> Still not clear how you reject {1, 6, 7}, unless you
> have an expensive operation assigning each number to
> its set of origin.
The 'transposed' sets contain all their set origins. I spoke too soon about having the answer. Thanks to jet lag I figured it out but I'm going to take a little more time to write some example code because I don't think I can explain it well otherwise.
This is the code to transpose the sets, but this is not hard part :-)
My concern is the algorithm to obtain the result sets. You said that it can be easly implemented with a "generic" recursive algorithm but I didn't find any good solution :(
(I don't use the code special token for easier cut 'n paste)
import java.util.*;
public class Combinations
{
static final int SET_NUMBER = 4;
static final int SET_SIZE= 3;
public static void main(String[] args)
{
Random rand = new Random(System.currentTimeMillis());
double resSetNum = 1;
int setNum = (int)((5+Math.round(rand.nextGaussian())*(SET_NUMBER-5)) + 1);
if (setNum <=0) setNum = 1;
//int setNum = SET_NUMBER;
//int setSize = SET_SIZE;
byte sets[][] = new byte[setNum][];
for (int k = 0; k < setNum; k++)
{
int setSize = (int)((5+Math.round(rand.nextGaussian())*(SET_SIZE-5)) + 1);
if (setSize <= 0) setSize = 1;
resSetNum *= setSize;
byte[] set = new byte[setSize];
byte base = (byte)rand.nextInt(5);
for (byte j = 0; j < setSize ; j++)
{
set[j] = (byte) (j + base);
}
sets[k] = set;
}
printSets(sets);
System.out.println("\n" + resSetNum + " full result sets");
LinkedList[] transposed = transpose(sets);
for (int k=0; k < transposed.length; k++)
{
if (transposed[k] != null)
{
System.out.print(k + ":" ); printList(transposed[k]);
}
}
}
public static LinkedList[] transpose(byte[][] sets)
{
//fixed lenght for performance improvement
//memory is not an issue
LinkedList[] result = new LinkedList[200];
for (byte k = 0; k < sets.length; k++)
{
byte[] set = sets[k];
for (byte j = 0; j < set.length; j++)
{
byte v = set[j];
if (result[v] == null) { result[v] = new LinkedList();}
result[v].add(new Byte(k));
}
}
return result;
}
static void printSets(byte[][] sets)
{
for (int k = 0; k < sets.length; k++)
{
System.out.print("{");
if (sets[k].length > 1) System.out.print(sets[k][0]);
for (int j = 1; j < sets[k].length ; j++) System.out.print("," + sets[k][j]);
System.out.println("}");
}
}
static void printList(List l)
{
Iterator it = l.iterator();
System.out.print("{");
if (it.hasNext()) System.out.print(it.next());
while (it.hasNext()) { System.out.print(","+it.next()); }
System.out.println("}");
}
}
Here's the naive algorithm. It will produce invalid sets as you pointed out. I'll post the validating algorithm later. It's a little more complicated.
//combine sets {1,2} {6,7} {1,2,3,4} into ordered list
static int[] source = {1,1,2,2,3,4,6,7};
static int recursionLevel = 0;
public static void main(String args[])
{
Collection permutations = permutations(3);
for (Iterator i = permutations.iterator(); i.hasNext(); )
{
System.out.println(arrayString((int[]) i.next()));
}
}
static Collection permutations(int length)
{
return permutations(length, source, 0, new int[length]);
}
static Collection permutations(int length, int[] source,
int start, int[] copy)
{
//recursionLevel++;
ArrayList results = new ArrayList();
for (int j = start; j < source.length - (length - 1); j++)
{
//System.out.println("recursion level: " + recursionLevel
//+ " copy: " + arrayString(copy) + " length: " + (copy.length - length));
int[] array = new int[copy.length];
System.arraycopy(copy, 0, array, 0, copy.length - length);
array[array.length - length] = source[j];
//System.out.println("recursion level: " + recursionLevel
//+ " array: " + arrayString(array));
if (length == 1)
{
results.add(array);
}
else
{
results.addAll(permutations(length - 1, source, j + 1, array));
// if the next number is the same, we've
// already created those permutations
while (j < source.length && source[j] == source[j + 1]) j++;
}
}
//recursionLevel--;
return results;
}
static String arrayString(int[] array)
{
StringBuffer buffer = new StringBuffer();
for (int j = 0; j < array.length; j++)
{
buffer.append(array[j]);
if (j < array.length - 1)
{
buffer.append(", ");
}
}
return buffer.toString();
}
error skipping in if; change to:while (j < (source.length - 1) && source[j] == source[j + 1]) j++;
> The 'transposed' sets contain all their set origins.I know, but ISTM you'll need a backtracking search to say which set provided the 1 - you can't just union the set origins and check the union is large enough.
> I know, but ISTM you'll need a backtracking search to
> say which set provided the 1 - you can't just union
> the set origins and check the union is large enough.
I think I figured out a way to do it. Intuitively I think it will work but you can look it over once I post it. Even if it works there's still a question about whether it is going to be more expensive than producing all the combinations and removing duplicates. I think it will depend on what the sets look like. The worst case senario for my process would be all mutually exclusive sets but the OP says that the sets are mostly overlapping.
I'll post it by the end of the day hopefully.
Definetely the will sets overlaps a lot.
To check if a set is valid we can use this method:
We associate a weight to each individual set, as the following:
Set 0 - weight W1 = 2^0
Set 1 - weight W2 = 2^1
...
Set n - weight Wn = 2^n
Then, to each value in the superset we associate the weight from its original set and, when we construct the result set, we just sum the weights of all the values in the result set. If the total weight is different than (W = W1+W2+...+Wn) the set is not valid.
But I am afraid that the algorithm suggested by dubwai (the "naive" one) is generating also duplicate sets, beside invalid ones :(
Example:
{12}{12}{123}
it produces three times the set {112}
Antonio.
> Example:
> {12}{12}{123}
> it produces three times the set {112}
That's a bug. I fixed it and here's the validating version. I will warn you, this code is not pretty and I am supplying the transposed and source list through hard coding. You said you had that part down so I'll leave it to you to fix it. There is also a weird combination of arrays and Collections in this code. I would go with one or the other in the end.
public class Garbage
{
Map sources;
int[] source = {1,1,1,2,2,3,4,6,7,7};
int recursionLevel = 0;
public Garbage()
{
sources = new HashMap();
HashSet sets = new HashSet();
sets.add(new Integer(1));
sets.add(new Integer(2));
sets.add(new Integer(3));
sources.put(new Integer(1), sets);
sets = new HashSet();
sets.add(new Integer(1));
sets.add(new Integer(3));
sources.put(new Integer(2), sets);
sets = new HashSet();
sets.add(new Integer(3));
sources.put(new Integer(3), sets);
sets = new HashSet();
sets.add(new Integer(3));
sources.put(new Integer(4), sets);
sets = new HashSet();
sets.add(new Integer(2));
sources.put(new Integer(6), sets);
sets = new HashSet();
sets.add(new Integer(2));
sets.add(new Integer(3));
sources.put(new Integer(7), sets);
}
public static void main(String args[])
{
Garbage garbage = new Garbage();
Collection permutations = garbage.permutations(3);
for (Iterator i = permutations.iterator(); i.hasNext(); )
{
int[] array = (int[]) i.next();
System.out.println(arrayString(array) + " valid? "
+ garbage.validatePermutation(array));
}
}
Collection permutations(int length)
{
return permutations(length, source, 0, new int[length]);
}
Collection permutations(int length, int[] source,
int start, int[] copy)
{
//recursionLevel++;
ArrayList results = new ArrayList();
for (int j = start; j < source.length - (length - 1); j++)
{
//System.out.println("recursion level: " + recursionLevel
//+ " copy: " + arrayString(copy) + " length: " + (copy.length - length));
int[] array = new int[copy.length];
System.arraycopy(copy, 0, array, 0, copy.length - length);
array[array.length - length] = source[j];
//System.out.println("recursion level: " + recursionLevel
//+ " array: " + arrayString(array));
if (length == 1)
{
results.add(array);
}
else
{
results.addAll(permutations(length - 1, source, j + 1, array));
}
while (j < (source.length - 1) && source[j] == source[j + 1]) j++;
}
//recursionLevel--;
return results;
}
public boolean validatePermutation(int[] array)
{
ArrayList sourceList = new ArrayList();
for (int j = 0; j < array.length; j++)
{
sourceList.add(new ValidationSet((Set) sources.get(new Integer(array[j]))));
}
for (int j = 0; sourceList.size() > 1; j++)
{
Collections.sort(sourceList, LengthComparator.INSTANCE);
ValidationSet a = (ValidationSet) sourceList.get(0);
sourceList.remove(0);
ValidationSet b = (ValidationSet) sourceList.get(0);
b.addAll(a);
b.incrementSources();
if (!b.isValid())
{
return false;
}
}
return true;
}
static String arrayString(int[] array)
{
StringBuffer buffer = new StringBuffer();
for (int j = 0; j < array.length; j++)
{
buffer.append(array[j]);
if (j < array.length - 1)
{
buffer.append(", ");
}
}
return buffer.toString();
}
}
class ValidationSet extends HashSet
{
int sources = 1;
public ValidationSet()
{
super();
}
public ValidationSet(Collection c)
{
super(c);
}
public void incrementSources()
{
sources++;
}
public boolean isValid()
{
return !(size() < sources);
}
}
class LengthComparator implements Comparator
{
static final Comparator INSTANCE = new LengthComparator();
public int compare(Object a, Object b)
{
return ((Collection) a).size() - ((Collection) b).size();
}
}
sorry one change to that:
public boolean validatePermutation(int[] array)
{
ArrayList sourceList = new ArrayList();
for (int j = 0; j < array.length; j++)
{
sourceList.add(new ValidationSet((Set) sources.get(new Integer(array[j]))));
}
for (int j = 0; sourceList.size() > 1; j++)
{
Collections.sort(sourceList, LengthComparator.INSTANCE);
ValidationSet a = (ValidationSet) sourceList.get(0);
sourceList.remove(0);
ValidationSet b = (ValidationSet) sourceList.get(0);
b.union(a);
if (!b.isValid())
{
return false;
}
}
return true;
}
class ValidationSet extends HashSet
{
int sources = 1;
public ValidationSet()
{
super();
}
public ValidationSet(Collection c)
{
super(c);
}
public void union(ValidationSet set)
{
addAll(set);
sources += set.sources;
}
public boolean isValid()
{
return !(size() < sources);
}
}
of course I'm not sure this will always work. I have not gone through a rigourous proof.
v. interesting thread!
here is some code for the naive implementation using Collections that might help
will you post the code if you get dubwais solution working?
asjf
import java.util.*;
public class Bianto {
static final int[][] typical = {
{1,2,3,4,5,6,7,8,9,10},
{3,4,5,6,7,8,9},
{4,5,6,7,8,9,10},
{4,5,6,7,8,9,10,11,12}};
public static void main(String [] args) {
List input = intAA2List(typical);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(f(input,new LinkedList()));
}
public static Set addStrictToAll(Set sets, Object element) {
Set result = new HashSet();
for(Iterator i = sets.iterator(); i.hasNext(); ) {
Set candidate = (Set) i.next();
if(candidate.add(element))
result.add(candidate);
}
return result;
}
public static Set f(List sets, LinkedList exclusion) {
Set result = new HashSet();
if(sets.size()==0) return new HashSet(Collections.singleton(new HashSet()));
for(Iterator i = ((Set) sets.get(0)).iterator(); i.hasNext(); ){
Object element = i.next();
if(!exclusion.contains(element)) {
exclusion.add(element);
result.addAll(addStrictToAll(f(sets.subList(1,sets.size()),exclusion),element));
exclusion.removeLast();
}
}
return result;
}
public static List intAA2List(int [][] i) {
List result = new ArrayList();
for(int x=0; x<i.length; x++) {
Set set = new HashSet();
for(int y=0; y><i[x].length; y++)
set.add(new Integer(i[x][y]));
result.add(set);
}
return result;
}
public static void print(Collection c) {
for(Iterator i = c.iterator(); i.hasNext(); )
System.out.println(i.next());
}
}>
asjfa at 2007-7-18 22:22:31 >
I'm trying to understand the algorithm used by the code above from dubwais
Only the code doesn't help me to validate the algorithm :(
But I'm implementing another very interesting technique and, if it works, of course I will post it here.
I agree with you, this thread is fascinating :-)
Antonio :)
> I'm trying to understand the algorithm used by the
> code above from dubwais
> Only the code doesn't help me to validate the
> algorithm :(
> But I'm implementing another very interesting
> technique and, if it works, of course I will post it
> here.
What my code does is put all the 'tranposed' sets into a list. It then sorts the list by length of sets so that the smallest sets are looked at first.
It then removes the first set in the list and unions it with the second one. At the same time it stores the number of sets in that union.
It checks to see if the size of the union is at least as large as the number of sets in the union. If the size of the union is smaller than the number of sets that have been added to it, that means that the set we are testing is not valid. Basically it means that at least one number in the set must be pulled from a source set that another number must be pulled from.
Lets take an example:
{1,2} {6,7} {1,2,3,4}
validate {1,6,7}
sources:
1 6 7
--
1 2 2
3
sort sources:
2 2 1
3
union first two:
2 1
3
fail: The first two sets contain only a single source set. No result set can be created from these two numbers.
Lets look at a more complicated example:
{1,2,3,4,5}
{1,5}
{1,2}
{1,5}
{4,5,6}
validate:
{1,3,4,5,6}
sources:
1 3 4 5 6
1 1 1 1 5
25 2
34
45
sort:
1 5 1 1 1
5 2 2
3 4
4 5
union first and resort:
2 1 1 1
-
1 1 1 1
5 5 2 2
3 4
4 5
union again:
3 1 1
-
1 1 1
5 2 2
3 4
4 5
fail: 2 sources for 3 numbers.
Does it mean that I have to store all the result sets in memory?
If so I can't implement it. Even with a big amount of memory I can't handle 10^20 sets of values :(
I implemented another algorithm instead and it seems working fine without using memory. It's the best so far.
Check this url out:
http://forums.devshed.com/showthread.php?s=&postid=251533#post251533
Antonio :)
> Does it mean that I have to store all the result sets
> in memory?
No. I merely did that for testing / verification purposes. You would want to verify each naive permutation immediately after creating it. I think there are some small optmizations that can be made here and maybe some big ones.
> If so I can't implement it. Even with a big amount of
> memory I can't handle 10^20 sets of values :(
As I say above, you can verify as you go and write out the sets to a stream as you find the valid ones.
Whether you end up using it or not, I had fun figuring this out. Good luck.
> Check this url out:
> http://forums.devshed.com/showthread.php?s=&postid=2515
> 3#post251533
Why is it the best? Depending on the number of overlapping numbers, my algorithm can use many less initial operations. For example:
{1,2,3} {1,2,3} {1,2,3}
The algorithm in the link will produce and check 27 sets.
My algorithm will produce and check 10.
I had fun too :)But thanks for your help. I will probably implement your algorithm and compare the two. It's very important for me to decrese the processing time.Great job dubwai.Antonio :)
> But thanks for your help. I will probably implement
> your algorithm and compare the two. It's very
> important for me to decrese the processing time.
I was thinking that if you really want to make this as fast as possible, you'll probably want to do a initial analysis of your input. At different thresholds of overlapping, you'll want to use different algorithms. The hard part is figuring out what your thresholds are. For example, if there is no overlapping it's going to be fastest to just use the obvious algorithm. With some overlapping the other algortithm you pasted a link to will probably be best. If there is much overlapping I'll guess that my algorithm will provide better performance.
Good luck again.
You are absolutely right.When I implement your algorithm in the right way (without using memory) I will post it here, along with a comparison report between the two (or three, as you suggested).Please, keep watching this thread.Antonio :)
Just to make sure I'm being clear, I mean that your final program should probably contain one or more algorithms. And for each set of sets, you would determine which one is most appropriate.
> Got it :-) A.When you get done with your initial development, I have an optimization for the validation code.
> Got it :-) A.please could you post the code?thanks,asjf
asjfa at 2007-7-18 22:22:36 >
I didn't finish implementing the algorithm suggested by dubwai but at this URL you can find some code that implements another nice algorithm.
You can find all the details in the discussion thread.
http://forums.devshed.com/showthread.php?s=&postid=251533#post251533
Antonio :)
hi, happy easter!
thanks for the link, I've downloaded the code but am having some problems understanding the output/algorithm :(
I tried it on {{1,2},{6,7},{1,2,3,4}} and was expecting the 10 results
[2, 4, 7] [2, 6, 1] [1, 3, 7] [4, 6, 1] [2, 6, 3]
[6, 1, 3] [2, 1, 7] [4, 1, 7] [2, 3, 7] [2, 4, 6]
but instead got
{1,1,6} {1,1,7} {1,2,6} {1,2,7} {1,3,6} {1,3,7} {1,4,6}
{1,4,7} {2,2,6} {2,2,7} {2,3,6} {2,3,7} {2,4,6} {2,4,7}
in which the correct 10 results are contained, but it also says
Number of total sets: 256.0
Number of valid sets: 14.0
Number of duplicate sets: 2.0
which I thought meant that there are 12 correct results?
On the other hand I don't understand why the algorithm works in the first place!
1) when you sort the sets its on the first element only (the sets are assumed ordered on input?). This will fail on inputs like
{{1,4,7},{1,4},{1,4,6},{1,3}}
(it remains unchanged). I've tried changing the code to
private static void orderSets(byte [][] input) {
Comparator c = new Comparator() {
public int compare(Object a, Object b) {
byte [] s = (byte[]) a, r = (byte[]) b;
int sl = s.length, rl = r.length, j=0;
while(j<sl && j><rl && s[j]==r[j]) j++;
return (j==sl || j==rl) ? (sl==rl ? 0 : (sl >< rl ? -1 : 1)) : (s[j] < r[j] ? -1 : 1);
}
};
Arrays.sort(input,c);
}
2) makeIntersections doesn't behave as I'd guess it should? calling this code below outputs {1,4}
byte [] set1= new byte [] {1,4,7};
byte [] set2= new byte [] {1,7};
byte [] result = findIntersection(set1,set2);
for(int j=0; j<result.length; j++)
System.out.print(result[j]);
System.out.println();
3) I don't get how restricting attention to two adjacent sets in the ordered array is something you can do when making a candidate result set. Sorry this is such a vague point..
anyway, hope you can help with this - I'd only just got my head round dubwais solution when this one turned up!
thanks,
asjf>
asjfa at 2007-7-18 22:22:36 >
asjf, I think you misunderstood the problem. [1, 1, 6] etc are valid output, because sets 1 and 3 can each provide a 1, and set 6 can provide a 6. The output required is the set of unordered elements of the Cartesian product of the input sets.
> asjf, I think you misunderstood the problem.
> [1, 1, 6] etc are valid output, because sets 1 and 3
> can each provide a 1, and set 6 can provide a 6. The
> output required is the set of unordered elements of
> the Cartesian product of the input sets.
goddamit! this is clear from the first post too..
thanks,
asjf
asjfa at 2007-7-18 22:22:36 >
I have not compared this algorithm with the others, but I think it will be one of the fastest. It is strictly iterative and does not generate any duplicate/invalid combinations.
The algorithm requires that the initial sets be sorted in order of the first entry of each set, but this would be trivial to include - I manually sorted them for the tests.
class Test {
int len;
int[] vals;// the current set
int[] order;// sorted list of indexes for current set
int[][] data;
Test(int[][] data) {
this.data = data;
len = data.length;
vals = new int[len];
order = new int[len];
for (int x = 0; x < len; x++) {// initialize first set
vals[x] = data[x][0];
}
for (int x = 0; x < len; x++) {// initialize order (data must be pre-sorted on first value)
order[x] = x;
}
int x;
do {
print(vals);
x = len;// current index to update
while (x > 0) {// stop when no value can be updated
x--;
if (++vals[x] <= data[x][1]) {// is val[x]+1 still valid
while (++x < len) {//set all other indexes to min allowed values
setMin(x);
}
break;
}
}
} while (x > 0);
}
void setMin(int idx) {
for (int x = idx-1; ;x--) {// find largest current value in lower indexes
if (vals[order[x]] <= data[idx][1]) {// that is in the current indexes range
vals[idx] = Math.max(vals[order[x]], data[idx][0]);
int y;
for (y = idx-1; y >= 0 && vals[idx] < vals[order[y]]; y--) {// update order
order[y+1] = order[y];
}
order[y] = x;
break;
}
}
}
void print(int[] val) {
for (int x = 0; x < val.length; x++) {
if (x == 0) {
System.out.print("{");
} else {
System.out.print(',');
}
System.out.print(val[x]);
}
System.out.println("}");
}
public static void main(String[] args) {
int[][] data = {{0,3},{1,5},{3,7},{4,6}};// since using consecutive values, only need first and last values
Test test = new Test(data); // data must be pre sorted by first value
}
}
pekoea at 2007-7-18 22:22:36 >
Oops. The correct code is below. After I wrote the previous program, I tried to optimize the code a bit, but did not test the changes properly.
class Test {
int len;
int[] vals;// the current set
int[][] data;
Test(int[][] data) {
this.data = data;
len = data.length;
vals = new int[len];
for (int x = 0; x < len; x++) {// initialize first set
vals[x] = data[x][0];
}
int x;
do {
print(vals);
x = len;// current index to update
while (x > 0) {// stop when no value can be updated
x--;
if (++vals[x] <= data[x][1]) {// is val[x]+1 still valid
while (++x < len) {//set all other indexes to min allowed values
setMin(x);
}
break;
}
}
} while (x > 0);
}
void setMin(int idx) {
vals[idx] = data[idx][0];
for (int x = 0; x < idx; x++) {
if (vals[x] <= data[idx][1]) {
vals[idx] = Math.max(vals[x], vals[idx]);
}
}
}
void print(int[] val) {
for (int x = 0; x < val.length; x++) {
if (x == 0) {
System.out.print("{");
} else {
System.out.print(',');
}
System.out.print(val[x]);
}
System.out.println("}");
}
public static void main(String[] args) {
int[][] data = {{0,3},{0,2},{3,9},{4,6}};// since using consecutive values, only need first and last values
Test test = new Test(data); // data must be pre sorted by first value
}
}
pekoea at 2007-7-18 22:22:36 >
I will test it and let you know :-)Antonio.
This algorithm is much faster than the one on the other forum.
On my computer, for 8 sets with 10 values each, it processes more than 3.3 millions valid sets in about 300 milliseconds (without printing of course). The algorithm from Nag, with the same input, it takes almost one minute to generate the same output.
This was my input: {{0,9},{0,9},{5,14},{5,14},{10,19},{10,19},{15,24},{15,24}}
Very Nice pekoe!
Antonio :)
All of the solutions that occured used primitive arrays.
If anyone wants to use the algorithm on arrays of any type, you should generate an int[][] array which references which position of which array to get the value from.
Here is some short code that does this.
public class IndexMaker {
public int[][] getIndexes(int[] maximums){
int total = 1;
for (int i = 0; i < maximums.length; i++) {
total*= maximums;
}
int[][] result = new int[total][];
int[] values = new int[maximums.length];
for( int i = 0 ; i < result.length; i++ ){
result = new int[maximums.length];
if( i == 0 ) continue;
increment(values, maximums, 0);
for (int j = 0; j < values.length; j++) {
result[j] = values[j];
}
}
return result;
}
public void increment(int[] values, int[] maximums, int i){
values ++;
if( values > maximums-1){
values = 0;
if( i+1 < values.length )
increment(values,maximums, i+1);
}
}
public static void main(String[] args) {
IndexMaker maker = new IndexMaker();
int[][] indexes = maker.getIndexes(new int[]{3,2,2,6});
for (int i = 0; i < indexes.length; i++) {
for (int j = 0; j < indexes.length; j++) {
System.out.print(indexes[j]+",");
}
System.out.println();
}
}
}
This seems to be pretty quick.
Cheers.
Joe
I happened to apply this Permutations with Sets in developement. I have tried few code snippets posted here.. but, couldnt get correct results..
Here is what I think is, generates all valid possible combinations in minimum number of loops.
number of loops = size of array times number of valid combinations
for 3 x 4 x 2 --> loops = 3 x 24.. ( please correct me if I'm wrong)
Here is the code,
public class MTCGenerator {
private int intCombs;
public MTCGenerator() {
}
public static void main(String[] args) throws Exception{
MTCGenerator maker = new MTCGenerator();
// Declare the array
String[][] values = {
{"1","2","3","4"},
{"1", "2","3"},
{"9"},
{"5","6"}
};
maker.print(maker.generate(values));
}
public String[][] generate(String[][] values) throws Exception{
// Total possible and valid elements
int TE = 1;
for(int vcount=0;vcount<values.length;vcount++){
TE *= values[vcount].length;
}
// To store results
String[][] R = new String[TE][values.length];
for(int colNum=0;colNum<values.length;colNum++){
int n = values[colNum].length;
int NL = 0; if(colNum==values.length-1) NL = 1;
else NL = values[colNum+1].length;
int NR = TE/NL;
//System.out.println("-\nTE\tcolNum\tn\tNL\tNR\n");
//System.out.print(TE+"\t"+colNum+"\t"+n+"\t"+NL+"\t"+NR);
//System.out.print("\n\ni\tLL\tHL\n");
for(int i=1;i<=NR;i++){
int LL = (i-1) * NL;
int HL = i * NL;
//System.out.print(i+"\t"+LL+"\t"+HL+"\n");
for(int j=LL;j<HL;j++){
R[j][colNum]=values[colNum][j%n];
}
}
}
return R;
}
public void print(String[][] result){
for(int i =0; i><result.length;i++){
for(int j=0;j<result.length;j++){
if(j==0) System.out.print("\n"+result[j]+"\t");
else System.out.print(result[j]+"\t");
}
}
}
}>
Wats up.. no comments/complements on my previous post? ..
There is a bug in that, when all sets have same number of elements.. it has been corrected .. it runs with no probs now.. If any body needs modified code, let me know
Shall I have DUKES? I can't wait to see dukes coming for first time !!
FWIW this is what I use
class Combinations1PerSet
{
public static void main(String[] args)
{
String array[][] = {{"00","01","02","03","04"},{"10","11"},{"20","21","22","23"}};
int ctr[] = new int[array.length];
String combo;
while(ctr[0] < array[0].length)
{
combo = "";
for(int i = 0; i < ctr.length; i++)
{
combo += "-"+array[i][ctr[i]];
}
combo = combo.substring(1);
System.out.println(combo);
ctr[ctr.length-1]++;
for(int i = ctr.length-1; i > 0; i--)
{
if(ctr[i] >= array[i].length)
{
ctr[i-1]++;
ctr[i] = 0;
}
else break;
}
}
System.exit(0);
}
}
> Shall I have DUKES? I can't wait to see dukes coming> for first time !!This thread is over 1 year old, and the posters problem has been solved !
