• Post Reply Bookmark Topic Watch Topic
  • New Topic

I cannot find the algorithm  RSS feed

 
Ali Akıllı
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Campbell Ritchie
Marshal
Posts: 56207
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
fred rosenberger
lowercase baba
Bartender
Posts: 12558
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56207
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 56207
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks a lot for your attention anyway. I will continue working.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!