programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Tim Cooke
• Devaka Cooray
• Ron McLeod
• Jeanne Boyarsky
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Piet Souris
• Carey Brown
• Tim Holloway
Bartenders:
• Martijn Verburg
• Frits Walraven
• Himai Minh

# I cannot find the algorithm

Greenhorn
Posts: 4
• Number of slices to send:
Optional 'thank-you' note:
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

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?

Marshal
Posts: 76888
366
• Number of slices to send:
Optional 'thank-you' note:
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 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
• Number of slices to send:
Optional 'thank-you' note:
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

Is it clear now?

lowercase baba
Posts: 13082
67
• Number of slices to send:
Optional 'thank-you' note:
What EXACTLY are your speed requirements here? 14,000 matrices doesn't seem like that much to me. What is the harm of computing them all and ignoring what you don't want?

Ali Akıllı
Greenhorn
Posts: 4
• Number of slices to send:
Optional 'thank-you' note:
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.

Campbell Ritchie
Marshal
Posts: 76888
366
• Number of slices to send:
Optional 'thank-you' note:
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 char[][][] size [24 × 24 × 24][4][3] would be feasible. But creating a Matrix object would be better than arrays.

Campbell Ritchie
Marshal
Posts: 76888
366
• Number of slices to send:
Optional 'thank-you' note:

Ali Akıllı wrote:By 4x3 matrices, I simply wanted to tell you the story.
. . .

I am afraid you have confused us by not telling us the whole 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.

Ali Akıllı
Greenhorn
Posts: 4
• Number of slices to send:
Optional 'thank-you' note:
Thanks a lot for your attention anyway. I will continue working.

 Where all the women are strong, all the men are good looking and all the tiny ads are above average: the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising