2 pair Combination of four values.

Hi,

I need to write a Java program for 2 pair Combination of four values.

Let’s say I have four letters.
X1,x2,y1,y2

Quote:

---

Rules:
1. Each letter can combine with another letter only once, and not with itself
2. Only 2 letter combinations
3. No redundancy

---

Quote:

---

The possible 2 pair values are
X1-x2
X1-y1
X1-y2
X2-y1
X2-y2
Y1-y2

---

May I know the algorithm (or java program) for six 2-pair combination?

With Regards and Respects,
Nandhini.

It's all about the permutations.

Did you tried out anything?

You can think about a simple logic in this case too.

Code:

---

class PermDemo {
    public static void main(String[] args) {
        tring[] sList = {"X1", "X2", "Y1", "Y2"};

        for(int i = 0; i < sList.length; i++) {
                        for(int j = i + 1; j < sList.length; j++) {
                                System.out.println(sList[i] + "-" + sList[j]);
                        }
                }
    }
}

---

By the way, you have posted this thread in a wrong sub-forum. I'll move it to the correct place this time. Please chose the correct sub-forum when you are posting again.

Quote:

---

Originally Posted by Eranga

It's all about the permutations.

---

:s/permut/combin/

kind regards,

Jos

Of course. A kind of possibilities we have.

Quote:

---

Originally Posted by Eranga

Of course. A kind of possibilities we have.

---

Yep, your algorithm is correct though ;-)

kind regards,

Jos

If OP could make something interesting from that, make sense to me. ;)

Respected Moderator Eranga,

I got the expected output by your coding.
I tried, but my coding lengthy comparing with your coding.

Quote:

---

Thank you .

---

With Regards and Respects,
Nandhini.

Post your code here. So I can comment on your code, if you like. :)

bumping an old thread.

I have a similar problem. I am trying to write a program that will write out all of the permutations of some letters. Say I want two letters and two of each letter: AABB. I want to get the 6 different ways to write those (AABB, ABAB, ABBA, BAAB, BABA, BBAA).

My first thoughts were to write a nested for loop with a for loop for each place a letter goes. But this wouldn't scale very well, as I want the program to be able to work for different numbers of letters.

I had some other ideas, but none have gone very far yet. Any suggestions?

Thanks

Yes, it is somewhat similar to the original question. However, it is even better start a new thread next time. Stick with this time only.

There is an easy way to achieve this. Recursively pick one character at a time and construct a new string by moving one letter at a time. Have a look at the sample code. Please note that I don't have test it and validate any results.

Code:

---

        private void allPermutations(String strNew, String strOriginal) {
                if(strOriginal.length() <= 1) {
                        System.out.println(strNew + strOriginal);
                }
                else {
                        for(int index = 0; index < strOriginal.length(); index++) {
                                try {
                                        String temp = strOriginal.substring(0, index) + strOriginal.substring(index + 1);
                                        allPermutations(strNew + strOriginal.charAt(index), temp);
                                }
                                catch (Exception ex) {
                                        ex.printStackTrace();
                                }
                        }
                }
        }

---

And also since the above code display all the permutations on your commbination you can see some duplicates. That means ABAB and ABAB is not the same. (Annoying ha..) Go through the code, try to identify the logic, apply into you code, compile it, run it and have a look at the result.

If you are stuck on anything or my code segment is no clear enough to you, please let me know. I'll explain them all.

Great, thanks Eranga!

Here is the code I have so far. I wrote a method to remove the duplicates and write it to a file, I also split the first ArrayList into 3 ArrayLists to make the Removing Duplicates faster.

edit: Sorry for the lack of comments in the code. Basically we send a string to allPerumtations() which puts all of the permutations into an ArrayList strList, then splitList() splits that into 3 different ArrayLists, remDups() removes the duplicates, and putInFile() writes to txt file.

Code:

---


import java.util.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
 
public class abc {
 
        final static String outFile = "abc4x3.txt";       
    static ArrayList<String> strList = new ArrayList<String>();
    static ArrayList<String> aList = new ArrayList<String>();
    static ArrayList<String> bList = new ArrayList<String>();
    static ArrayList<String> cList = new ArrayList<String>();
    static ArrayList<String> finalList = new ArrayList<String>();
   
 
    public final static void main(String[] args) throws Exception {
            allPermutations("", "AAAABBBBCCCC");
            splitList();
            remDups();
              putInFile();
           
    }
 
    private static void allPermutations(String strNew, String strOriginal) {
           
            if(strOriginal.length() <= 1) {
                    System.out.println(strNew + strOriginal);
                    strList.add(strNew + strOriginal);
            }
            else {
                    for(int index = 0; index < strOriginal.length(); index++) {
                            try {
                                    String temp = strOriginal.substring(0, index) + strOriginal.substring(index + 1);
                                    allPermutations(strNew + strOriginal.charAt(index), temp);             
                                  }
                            catch (Exception ex) {
                                    ex.printStackTrace();
                            }
                    }
            }
    }
   
    private static void remDups() {
            System.out.println(strList.size());
           
            // Remove from aList
            for (int i = aList.size() - 1; i >= 0; i--) {
                    //Remove duplicates
                    while (aList.indexOf(aList.get(i)) >= 0) { //While there are duplicates
                            int remove = aList.indexOf(aList.get(i));
                            System.out.println("i: " + i + " rem: " + remove);
                            if (remove != i) {
                                    aList.remove(remove);                          //Remove duplicates
                                    i--;
                            }
                            else break;
                    }       
            }
            // Remove from bList
            for (int i = bList.size() - 1; i >= 0; i--) {
                    //Remove duplicates
                    while (bList.indexOf(bList.get(i)) >= 0) { //While there are duplicates
                            int remove = bList.indexOf(bList.get(i));
                            System.out.println("i: " + i + " rem: " + remove);
                            if (remove != i) {
                                    bList.remove(remove);                          //Remove duplicates
                                    i--;
                            }
                            else break;
                    }       
            }
            // Remove from cList
            for (int i = cList.size() - 1; i >= 0; i--) {
                    //Remove duplicates
                    while (cList.indexOf(cList.get(i)) >= 0) { //While there are duplicates
                            int remove = cList.indexOf(cList.get(i));
                            System.out.println("i: " + i + " rem: " + remove);
                            if (remove != i) {
                                    cList.remove(remove);                          //Remove duplicates
                                    i--;
                            }
                            else break;
                    }       
            }
           
            /*
            for (int i = 0; i < strList.size(); i++) {
                    System.out.println(strList.get(i));
            }
            System.out.println("number of instances: " + strList.size());
            */
    }
   
   
    private static void putInFile() {
            // Open file for writing
            try {
                      wr = new PrintWriter(new FileWriter(outFile));
              }
              catch (IOException ex) {
                      System.out.println("Error: Adfjke---ji34");
              }
           
            // Write to file
            // Write aList to file
              for (int i = 0; i < aList.size(); i++) {
                        wr.println(aList.get(i));
                }
            // Write bList to file
            for (int i = 0; i < bList.size(); i++) {
                        wr.println(bList.get(i));
                }
            // Write cList to file
            for (int i = 0; i < cList.size(); i++) {
                        wr.println(cList.get(i));
                }
           
            System.out.println(aList.size());
            System.out.println(bList.size());
            System.out.println(cList.size());
            // Close file
            wr.close();           
    }
   
    private static void splitList() {
            for (int i = 0; i < strList.size(); i++) {
                    if (strList.get(i).charAt(0) == 'A') aList.add(strList.get(i));
                    else if (strList.get(i).charAt(0) == 'B') bList.add(strList.get(i));
                    else cList.add(strList.get(i));                   
            }
            for (int i = 0; i < aList.size(); i++) {
                    System.out.println(aList.get(i));
            }
            System.out.println(aList.size());
            System.out.println(bList.size());
            System.out.println(cList.size());
           
           
    }
   
    static PrintWriter wr;
}

---

This works really well for "AAABBBCCC", but when trying "AAAABBBBCCCC" or "AAAAABBBBBCCCCC" the program slows way down and runs out of memory when creating the initial strList (relatively early on). Is there a way to make this code run faster/with less redundancy? I notice when I just have the allPermutations() method println the results and not put them in the ArrayList it goes much much faster. Is there something better to use than an ArrayList?

Thanks

Maybe an easier approach (it also takes much less memory) is:

1) given any permutation P(0) P(1) P(2) P(3) ... P(n)
2) find the rightmost i such that P(i) < P(i+1)
3) if no such i can be found, stop
4) find the rightmost j > i such that P(j) > P(i) (such j always exists)
5) swap P(i) and P(j)
6) reverse P(i+1) ... P(n)
7) a new permutation P(0) ... P(n) has been found, go to step 2

kind regards,

Jos

Thanks a lot for your help Jos. I keep getting stuck though. I can get my program to solve for small string "AABB" but not for big strings. I feel like I've tried everything and I'm not sure what else to try..

Maybe I didn't understand your approach well. I think I confused step 2. What does i represent there? I took it as the last char in the string that is the same as the first one but has different chars behind it, rereading it I'm pretty sure I'm wrong.

Here is the code I have right now:

Code:

---

  private static void allPermutations(String str, char initChar) {
            strList.add(str);
            //for (int i = 0; i < str.length(); i++) {
            int rightMost = findRM(str, initChar);
               
            while (rightMost != -1) {
                    rightMost = findRM(str,initChar);
                    if (rightMost == -1) break;
                   
                    str = switchIt(rightMost, str);                   
                    System.out.println("switchIt: " + str);
                    strList.add(str);                // .replace()
                   
                    /* Experimenting, if rightMost moves to right use it, if not use old one
                    int rightMostNew = findRM(str, initChar);
                    if (rightMostNew == -1) break;
                    if (rightMostNew > rightMost) rightMost = rightMostNew;
                    */
                   
                    System.out.println("Before reversing:: rightMost, str: " + rightMost + str);
                                     
                    str = reverse(rightMost + 1, str);
                    strList.add(str);
                    System.out.println("reversed: " + str);
                    System.out.println("strList.size = " + strList.size());
            }
    }
                   
    //Find the right most i where substring after i is !allSameChar, if none return -1
    private static int findRM(String str, char ch) {
            int rightMost = str.lastIndexOf(ch);
            while (allSameChar(str.substring(rightMost), ch)) {                // While substring after rM is all initChar
                    rightMost = str.lastIndexOf(ch, rightMost-1);
                    System.out.println(rightMost);
                    if (rightMost == -1) {
                            break;
                    }
            }
            return rightMost;
    }
   
    private static boolean allSameChar(String str, char ch) {
            boolean bol = true;
                    for (int i = 0; i < str.length(); i++) {
                            if (str.charAt(i) != ch) {
                                    bol = false;
                                    break;
                            }
                    }
            return bol;
    }
   
    private static String switchIt(int rightMost, String str) {
            String temp = "";
            temp += str.substring(0, rightMost);
            temp += str.charAt(rightMost + 1);
            temp += str.charAt(rightMost);
            temp += str.substring(rightMost + 2);
            return temp;
    }
   
    private static String reverse(int rev, String str) {
            String temp = "";
            String returnStr = str.substring(0, rev + 1);
            System.out.println("returnStr: " + returnStr);
            temp = str.substring(rev + 1);
            System.out.println("temp: " + temp);
            for (int i = temp.length() - 1; i >= 0; i--) {
                    returnStr += temp.charAt(i);
            }
            return returnStr;       
    }

---

Quote:

---

Originally Posted by atomant

Thanks a lot for your help Jos. I keep getting stuck though. I can get my program to solve for small string "AABB" but not for big strings. I feel like I've tried everything and I'm not sure what else to try..

Maybe I didn't understand your approach well. I think I confused step 2. What does i represent there? I took it as the last char in the string that is the same as the first one but has different chars behind it, rereading it I'm pretty sure I'm wrong.

---

The value i is an index value; here's a small example that implements the algotihm I outlined; it generates all permutations in lexicograpical order and it can handle duplicate values.

Code:

---

import java.util.Arrays;

public final class Permutation {
       
        private Permutation() { }
       
        private static void swap(int[] s, int i, int j) {
                int t= s[i]; s[i]= s[j]; s[j]= t;
        }
       
        public static boolean permute(int[] s) {
               
                int i, j;
               
                for (i= s.length-1; --i >= 0;)
                        if (s[i] < s[i+1])
                                break;
               
                if (i < 0) return false;
               
                for (j= s.length; --j > i;)
                        if (s[i] < s[j])
                                break;
               
                swap(s, i, j);
               
                for (j= s.length; ++i < --j;)
                        swap(s, i, j);
               
                return true;
        }
       
        public static void main(String[] args) {
               
                int[] s= { 1, 2, 3 };

                do {
                        System.out.println(Arrays.toString(s));
                }
                while (Permutation.permute(s));
        }
}

---

kind regards,

Jos

Thank you Jos, I'll look that over. Your method looks much nicer than than the method I'm working on.

I just got this working taking a different route. I broke the string into smaller pieces and took the combinations of those. In case anyone is interested here is some sloppy code:

Code:

---

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;

public class Permutate {
   
        static ArrayList<String> strList = new ArrayList<String>();
        static ArrayList<String> finalList = new ArrayList<String>();
        final static String outFile = "5x3.txt";
        static String[] strArr2 = { "AAA", "AAB", "AAC", "ABA", "ABB", "ABC", "ACA", "ACB", "ACC",
                    "BBB", "BBA", "BAA", "BAB", "BAC", "BBC", "BCA", "BCB", "BCC",
                    "CCC", "CCA", "CCB", "CAA", "CAB", "CAC", "CBA", "CBB", "CBC",};
        static String[] strArr = { "AAAAA", "AAAAB", "AAAAC", "AAABA", "AAABB", "AAABC", "AAACA", "AAACB", "AAACC", "AABAA", "AABAB", "AABAC", "AABBA", "AABBB", "AABBC", "AABCA", "AABCB", "AABCC", "AACAA", "AACAB", "AACAC", "AACBA", "AACBB", "AACBC", "AACCA", "AACCB", "AACCC", "ABAAA", "ABAAB", "ABAAC", "ABABA", "ABABB", "ABABC", "ABACA", "ABACB", "ABACC", "ABBAA", "ABBAB", "ABBAC", "ABBBA", "ABBBB", "ABBBC", "ABBCA", "ABBCB", "ABBCC", "ABCAA", "ABCAB", "ABCAC", "ABCBA", "ABCBB", "ABCBC", "ABCCA", "ABCCB", "ABCCC", "ACAAA", "ACAAB", "ACAAC", "ACABA", "ACABB", "ACABC", "ACACA", "ACACB", "ACACC", "ACBAA", "ACBAB", "ACBAC", "ACBBA", "ACBBB", "ACBBC", "ACBCA", "ACBCB", "ACBCC", "ACCAA", "ACCAB", "ACCAC", "ACCBA", "ACCBB", "ACCBC", "ACCCA", "ACCCB", "ACCCC", "BAAAA", "BAAAB", "BAAAC", "BAABA", "BAABB", "BAABC", "BAACA", "BAACB", "BAACC", "BABAA", "BABAB", "BABAC", "BABBA", "BABBB", "BABBC", "BABCA", "BABCB", "BABCC", "BACAA", "BACAB", "BACAC", "BACBA", "BACBB", "BACBC", "BACCA", "BACCB", "BACCC", "BBAAA", "BBAAB", "BBAAC", "BBABA", "BBABB", "BBABC", "BBACA", "BBACB", "BBACC", "BBBAA", "BBBAB", "BBBAC", "BBBBA", "BBBBB", "BBBBC", "BBBCA", "BBBCB", "BBBCC", "BBCAA", "BBCAB", "BBCAC", "BBCBA", "BBCBB", "BBCBC", "BBCCA", "BBCCB", "BBCCC", "BCAAA", "BCAAB", "BCAAC", "BCABA", "BCABB", "BCABC", "BCACA", "BCACB", "BCACC", "BCBAA", "BCBAB", "BCBAC", "BCBBA", "BCBBB", "BCBBC", "BCBCA", "BCBCB", "BCBCC", "BCCAA", "BCCAB", "BCCAC", "BCCBA", "BCCBB", "BCCBC", "BCCCA", "BCCCB", "BCCCC", "CAAAA", "CAAAB", "CAAAC", "CAABA", "CAABB", "CAABC", "CAACA", "CAACB", "CAACC", "CABAA", "CABAB", "CABAC", "CABBA", "CABBB", "CABBC", "CABCA", "CABCB", "CABCC", "CACAA", "CACAB", "CACAC", "CACBA", "CACBB", "CACBC", "CACCA", "CACCB", "CACCC", "CBAAA", "CBAAB", "CBAAC", "CBABA", "CBABB", "CBABC", "CBACA", "CBACB", "CBACC", "CBBAA", "CBBAB", "CBBAC", "CBBBA", "CBBBB", "CBBBC", "CBBCA", "CBBCB", "CBBCC", "CBCAA", "CBCAB", "CBCAC", "CBCBA", "CBCBB", "CBCBC", "CBCCA", "CBCCB", "CBCCC", "CCAAA", "CCAAB", "CCAAC", "CCABA", "CCABB", "CCABC", "CCACA", "CCACB", "CCACC", "CCBAA", "CCBAB", "CCBAC", "CCBBA", "CCBBB", "CCBBC", "CCBCA", "CCBCB", "CCBCC", "CCCAA", "CCCAB", "CCCAC", "CCCBA", "CCCBB", "CCCBC", "CCCCA", "CCCCB", "CCCCC" };
       
        public static void main(String[] args) {
      combine();
      //trim();
      toFile();
     
      System.out.println("final: " + finalList.size());
     
    }
 
    private static void combine() {
            String str = "";
            for (int i = 0; i< strArr.length; i++) {
                    for (int j = 0; j< strArr.length; j++) {
                            for (int k = 0; k< strArr.length; k++) {
                                    str = strArr[i] + strArr[j] + strArr[k];
                                    //strList.add(str);
                                    trim(str);
                                    System.out.println(str + " " + finalList.size());
                            }
                    }
            }
    }
   
    private static void trim(String str) {
            int aCount = 0, bCount = 0, cCount = 0;
            for (int j = 0; j < str.length(); j++) {
                    if (str.charAt(j) == 'A') aCount++;
                    if (str.charAt(j) == 'B') bCount++;
                    if (str.charAt(j) == 'C') cCount++;
            }
           
            if (aCount == 5 && bCount == 5) {                        // THIS NEED TO BE CHANGED WITH DIFFERENT SIZED ARRAYS
                    finalList.add(str);
                    System.out.println("KEEP:                " + str);
            }
            aCount = 0;
            bCount = 0;
            cCount = 0;
    }
   
   
    public static void toFile() {
            // Open file for writing
            try {
                      wr = new PrintWriter(new FileWriter(outFile));
              }
              catch (IOException ex) {
                      System.out.println("Error: Adfjke---ji34");
              }
              for (int i = 0; i < finalList.size(); i++) {
                    wr.println(finalList.get(i));
              }
              wr.close();
        }
   
    static PrintWriter wr;
}

---