Friday, July 19, 2024

 Sample program to count the number of different triplets (a, b, c) in which a occurs before b and b occurs before c from a given array.

Solution: Generate all combinations in positional lexicographical order for given array using getCombinations method described above. Select those with size 3. When selecting the elements, save only their indexes, so that we can determine they are progressive. 

 

class solution {

 

public static void getCombinations(List<Integer> elements, int N, List<List<Integer>> combinations) { 

      for (int i = 0; i < (1<<N); i++) { 

          List<Integer> combination = new ArrayList<>(); 

          for (int j = 0; j < elements.size(); j++) { 

              if ((i & (1 << j)) > 0) { 

                combination.add(j); 

              } 

          } 

          List<Integer> copy = new ArrayList<Integer>(combination); 

          combinations.add(copy); 

      } 

   }

 public static void main (String[] args) {

                  List<Integer> elements = Arrays.asList(1,2,3,4);

List<List<Integer>> indices = new ArrayList<Integer>();

        getCombinations(elements, elements.size(), indices);

        indices.stream().filter(x -> x.size() == 3)  

                      .filter(x -> x.get(0) < x.get(1)  && x.get(1) < x.get(2)) 

                       .forEach(x -> printList(elements, x)); 

       }

 

public static void printList(List<Integer> elements, List<Integer> indices) {

                 StringBuilder sb = new StringBuilder();

                 for (int i = 0; i < indices.size(); i++) {

                        sb.append(elements.get(indices.get(i)) + " "); 

                 }

                 System.out.println(sb.toString());

}

}

/* sample output:

1 2 3 

1 2 4 

1 3 4 

2 3 4

 */


No comments:

Post a Comment