Ali Akıllı

Greenhorn

Posts: 4

posted 2 years ago

For some years I have been working on a project. The project has come to a point where an optimization requires. But, I don't know how to do it. I am an amateur in JAVA btw.

I create matrices; 4X3 String matrices let's say. Each column of the matrix is a 1D-Array of Strings. Each array consists of the letters {a,b,c,d}. Hence, to create a matrix I generate three 1D-Arrays of Strings.

My objective is to generate all possible 4X3 matrices whith all combinations of the letters {a,b,c,d}.

I do these by the following program segment. Please have a look.

Once I generate my matrices, I do my calculations (that I did not include here) below. I need to create all those combinations and the algorithm that I gave above works perfectly.

So far so good. The problem is the rest. The project has come to a point that I do NOT need to do my computations for all (i,j,k) triplets of the for-loops! I need a clearing (omit, drop) of (i,j,k) triplets. I do NOT want to do my calculations for all (i,j,k) that is 24x24x24=13.824 times.

I need all the combinations of the string {a,b,c,d} and these three for-loops, but I do not need all (i,j,k) triplets. So, some (i,j,k) triplets should be droped; the calculations (that I did not include here) should not be done for those triplets.

To drop those triplets, I need to apply two processes that I described at the end of my first message. If we suppose that two methods are independent from each other, then the first method is trivial: that is "do the calculations if i<=j<=k". But, what about the second one?

There are two rules to achieve this clearing.

1) If I have generated the matriks (i,j,k)=(0,1,6), I do not need any exchange of the columns. That is I do not need any of matrices (1,0,6), (1,6,0), (0,6,1), (6,1,0) etc.

2) If we can reach matrix (i',j',k') from a matrix (i,j,k) by interchanging any two letters in every column, then we do not need to generate one of them.

Ex. from matrix (0,1,2), we reach matrix (6,7,8) by interchanging 'a' and 'b' in (0,1,2). That is,

0 abcd 1 abdc 2 acbd

6 bacd 7 badc 8 bcad

Anybody has any suggestion to do it? How can I aplly these two methods to for-loops to clear some of (i,j,k) triplets?

I create matrices; 4X3 String matrices let's say. Each column of the matrix is a 1D-Array of Strings. Each array consists of the letters {a,b,c,d}. Hence, to create a matrix I generate three 1D-Arrays of Strings.

My objective is to generate all possible 4X3 matrices whith all combinations of the letters {a,b,c,d}.

I do these by the following program segment. Please have a look.

Once I generate my matrices, I do my calculations (that I did not include here) below. I need to create all those combinations and the algorithm that I gave above works perfectly.

So far so good. The problem is the rest. The project has come to a point that I do NOT need to do my computations for all (i,j,k) triplets of the for-loops! I need a clearing (omit, drop) of (i,j,k) triplets. I do NOT want to do my calculations for all (i,j,k) that is 24x24x24=13.824 times.

I need all the combinations of the string {a,b,c,d} and these three for-loops, but I do not need all (i,j,k) triplets. So, some (i,j,k) triplets should be droped; the calculations (that I did not include here) should not be done for those triplets.

To drop those triplets, I need to apply two processes that I described at the end of my first message. If we suppose that two methods are independent from each other, then the first method is trivial: that is "do the calculations if i<=j<=k". But, what about the second one?

There are two rules to achieve this clearing.

1) If I have generated the matriks (i,j,k)=(0,1,6), I do not need any exchange of the columns. That is I do not need any of matrices (1,0,6), (1,6,0), (0,6,1), (6,1,0) etc.

2) If we can reach matrix (i',j',k') from a matrix (i,j,k) by interchanging any two letters in every column, then we do not need to generate one of them.

Ex. from matrix (0,1,2), we reach matrix (6,7,8) by interchanging 'a' and 'b' in (0,1,2). That is,

0 abcd 1 abdc 2 acbd

6 bacd 7 badc 8 bcad

Anybody has any suggestion to do it? How can I aplly these two methods to for-loops to clear some of (i,j,k) triplets?

Campbell Ritchie

Marshal

Posts: 56207

171

posted 2 years ago

Welcome to the Ranch

I am afraid I am finding your requirements difficult to follow. Please draw a diagram showing an example of the matrices you require. Put the diagram in code tags and (maybe) change the word java at the left to text. It will look a lot better.

You say combinations: there are only 4 combinations of 3 out of 4 items: {abc} {abd} {acd} {bcd}. That is worked out using

Why are you using substrings? There must be an easier way to achieve what you want.

I am afraid I am finding your requirements difficult to follow. Please draw a diagram showing an example of the matrices you require. Put the diagram in code tags and (maybe) change the word java at the left to text. It will look a lot better.

You say combinations: there are only 4 combinations of 3 out of 4 items: {abc} {abd} {acd} {bcd}. That is worked out using

*n*! ÷ (*n*! ×*r*!). If you put those into a 12‑element matrix, there are not more than 4¹² (= 16777216) different matrices if you are allowed to use any combination anywhere.Why are you using substrings? There must be an easier way to achieve what you want.

Ali Akıllı

Greenhorn

Posts: 4

posted 2 years ago

Hello Campbell Ritchie.

Thanks a lot for your message.

My strings consist of 4 letters {a,b,c,d}. We can construct 4!=24 different words from these four letters. Using each combination, I generate 4X3 matrices. For example, one of the matrices is as follow:

Each column is one of the combinations of {a,b,c,d}. Since we have 3 columns, there are 24x24x24=13.824 matrices (all possible combinations). To construct a 4x3 matrix, I have 3 for-loops.

First thing to state is that I need to generate 24 strings (because I will use them later). And "comb" method produces these strings. comb method provides us the strings with a number. For example, 0=abcd, 1=abdc, 2=acbd, 6=bacd, 7=badc 8=bcad, 17=cdba, 19=dacb, 23=dcba. Perfect!

The problem is in the rest of the program. I do not need to generate all those 13.824 matrices. And, this means that I will not run my calculations (that I did not include here) for some (i,j,k) triplets in the for-loops.

I do not know which (i,j,k) triplets I need. But, I know what I do not need.

Basically there are two rule to omit those matrices.

1) If we have already generated the matrix (i,j,k)=(0,1,2)=(abcd,abdc,acbd) and so done all the calculations that I did not include here, then we do not need to generate its column permutations. That is we do not need to generate (0,2,1), (1,0,2), (1,2,0), (2,1,0) and (2,0,1).

2) If we can reach matrix (i',j',k') from a matrix (i,j,k) by interchanging any two letters in every column, then we do not need to generate one of them.

Ex. from matrix (0,1,2), we reach matrix (6,7,8) by interchanging 'a' and 'b' in (0,1,2). That is,

0 abcd 1 abdc 2 acbd

6 bacd 7 badc 8 bcad

Is it clear now?

Thanks a lot for your message.

My strings consist of 4 letters {a,b,c,d}. We can construct 4!=24 different words from these four letters. Using each combination, I generate 4X3 matrices. For example, one of the matrices is as follow:

Each column is one of the combinations of {a,b,c,d}. Since we have 3 columns, there are 24x24x24=13.824 matrices (all possible combinations). To construct a 4x3 matrix, I have 3 for-loops.

First thing to state is that I need to generate 24 strings (because I will use them later). And "comb" method produces these strings. comb method provides us the strings with a number. For example, 0=abcd, 1=abdc, 2=acbd, 6=bacd, 7=badc 8=bcad, 17=cdba, 19=dacb, 23=dcba. Perfect!

The problem is in the rest of the program. I do not need to generate all those 13.824 matrices. And, this means that I will not run my calculations (that I did not include here) for some (i,j,k) triplets in the for-loops.

I do not know which (i,j,k) triplets I need. But, I know what I do not need.

Basically there are two rule to omit those matrices.

1) If we have already generated the matrix (i,j,k)=(0,1,2)=(abcd,abdc,acbd) and so done all the calculations that I did not include here, then we do not need to generate its column permutations. That is we do not need to generate (0,2,1), (1,0,2), (1,2,0), (2,1,0) and (2,0,1).

2) If we can reach matrix (i',j',k') from a matrix (i,j,k) by interchanging any two letters in every column, then we do not need to generate one of them.

Ex. from matrix (0,1,2), we reach matrix (6,7,8) by interchanging 'a' and 'b' in (0,1,2). That is,

0 abcd 1 abdc 2 acbd

6 bacd 7 badc 8 bcad

Is it clear now?

Ali Akıllı

Greenhorn

Posts: 4

posted 2 years ago

By 4x3 matrices, I simply wanted to tell you the story.

So far, I have computed for (column,row)=(3,4), (4,4),...,(7,4) and (3,5) and (4,5).

But, I need (8,4), (5,5) and (6,5)

The number of all possible matrices are,

(8,4)=110.075.314.176

(5,5)=24.883.200.000

(6,5)=2.985.984.000.000

If I can clear (drop, omit) those unnecessary matrices, they become computable in a reasonable time.

So far, I have computed for (column,row)=(3,4), (4,4),...,(7,4) and (3,5) and (4,5).

But, I need (8,4), (5,5) and (6,5)

The number of all possible matrices are,

(8,4)=110.075.314.176

(5,5)=24.883.200.000

(6,5)=2.985.984.000.000

If I can clear (drop, omit) those unnecessary matrices, they become computable in a reasonable time.

Campbell Ritchie

Marshal

Posts: 56207

171

posted 2 years ago

I have edited your post to add code tags and additional spaces and doesn't it look better

What you want is matrices with one letter in each of the locations and no duplication in the rows. You can create the twenty‑four rows and maybe keep a List<Row> and identify each by a number 0…23. You can fill each element with loops, though I suspect recursion or use of a Stream might be better.

As Fred says, if you only have 24³ possible matrices, you can create them all. Even a

What you want is matrices with one letter in each of the locations and no duplication in the rows. You can create the twenty‑four rows and maybe keep a List<Row> and identify each by a number 0…23. You can fill each element with loops, though I suspect recursion or use of a Stream might be better.

As Fred says, if you only have 24³ possible matrices, you can create them all. Even a

`char[][][]`size [24 × 24 × 24][4][3] would be feasible. But creating a Matrix object would be better than arrays.
Campbell Ritchie

Marshal

Posts: 56207

171

posted 2 years ago

Please write down in plain simple English/French/Swahili/Tagalog/Hindi/other language what you intend to do. Do you want 5 letters across the row chosen from {a, b, c, d}? Or are you choosing them from a different set? If you are not interested in duplicates caused by swapping letters, you have moved from permutations to combinations; there are as I said earlier only 4 combinations of 3 out of 4, so your task becomes much simpler.

I am afraid you have confused us by not telling us the whole story.Ali Akıllı wrote:By 4x3 matrices, I simply wanted to tell you the story.

. . .

Please write down in plain simple English/French/Swahili/Tagalog/Hindi/other language what you intend to do. Do you want 5 letters across the row chosen from {a, b, c, d}? Or are you choosing them from a different set? If you are not interested in duplicates caused by swapping letters, you have moved from permutations to combinations; there are as I said earlier only 4 combinations of 3 out of 4, so your task becomes much simpler.