Geek Answers Handbook

Algorithm to maximize the distance (avoid repeating) of selection elements from sets

I am looking for an algorithm that successfully generalizes the following problem to n number of sets, but for simplicity we assume that there are 4 different sets, each of which contains 4 elements. It can also be assumed that each set always contains an equal number of elements, but there can be any number of elements. Therefore, if the first set contains 37 elements, we can assume that each of the other sets contains 37 elements.

The combination of elements is formed by taking 1 element from the first set and placing it in first place, 1 element from the second set and placing it in second place, etc. For example, the first set contains {A 0, A 1, A 2, A 3}, the second set contains {B 0, B 1, B 2, B 3}, the third is {C 0, C 1, C 2, C 3} and the fourth is {D 0, D <sub> 1sub>, D <sub> 2sub>, D <sub> 3sub>}. One possible combination would be [A 0, B 2, C 1, D 3].

The goal is to find a path that maximizes distance while cycling through all possible combinations, avoiding repeating as much as possible. And avoidance of repetition applies to adjacent groups, as well as to individual columns. For instance:


  • Individual columns

    • [A 0, B 0, C 0, D 0]
    • [A 1, B 1, C 1, D 1]
    • [A 2, B 0, C 2, D 2]

This is not true because B 0 repeated earlier than it should have been.


  1. Related Groups

    • [A 0, B 0, C 0, D 0]
    • [A 1, B 1, C 1, D 1]
    • [A 2, B 2, C 2, D 2]
    • [A 3, B 3, C 3, D 3]
    • [A 0, B 0, C 1, D 2]

This is not true because the adjacent pair (A 0, B 0) was repeated earlier than it should have been. However, if the latter was instead of [A 0, B 1, C 0, D 1], then that would be good.


, , . , (A 0, B 0), .

, 3 , n 4 . ?


?

, . 3x3 , , ( ) :

(A0,B0,C0)1, (A1,B0,C1)4, (A2,B0,C2)7    (A0,B0,C1)13, (A1,B0,C2)16, (A2,B0,C0)10    (A0,B0,C2)25, (A1,B0,C0)19, (A2,B0,C1)22

(A0,B1,C0)8, (A1,B1,C1)2, (A2,B1,C2)5    (A0,B1,C1)11, (A1,B1,C2)14, (A2,B1,C0)17    (A0,B1,C2)23, (A1,B1,C0)26, (A2,B1,C1)20

(A0,B2,C0)6, (A1,B2,C1)9, (A2,B2,C2)3    (A0,B2,C1)18, (A1,B2,C2)12, (A2,B2,C0)15    (A0,B2,C2)21, (A1,B2,C0)24, (A2,B2,C1)27

, (, ), . , :

@Test
public void run() {

    List<String> A = new ArrayList<String>();
    A.add("0");
    A.add("1");
    A.add("2");
    List<String> B = new ArrayList<String>();
    B.add("0");
    B.add("1");
    B.add("2");
    List<String> C = new ArrayList<String>();
    C.add("0");
    C.add("1");
    C.add("2");

    int numElements = A.size();

    List<String> output = new ArrayList<String>();

    int offset = 0;
    int nextOffset = 0;

    for (int i = 0; i < A.size()*B.size()*C.size(); i++) {

        int j = i % numElements;
        int k = i / numElements;

        if (j == 0 && k%numElements == numElements-1) {
            nextOffset = (j+k+offset) % numElements;
        }

        if (j == 0 && k%numElements == 0) {
            offset = nextOffset;
        }

        String first = A.get((j+k+offset) % numElements);
        String second = B.get(j);
        String third = C.get((j+k) % numElements);

        System.out.println(first + " " + second + " " + third);
        output.add(first + second + third);
    }

}

, , , (A 0, B 1) , 8 11:( , , , , ?.. ! ,


, , .

, , , , , . , 3 3 , 3 . 27 - , , , !

, 3 , , 3 3, . , , 10 , 1000 . , , , , . , , , , - , numElements 2. 3 5 25 :

19) A1 B3 C1
20) A2 B4 C2
21) A4 B0 C4 < -
22) A0 B1 C0
23) A1 B2 C1
24) A2 B3 C2
25) A3 B4 C3
26) A0 B0 C4 < -
27) A1 B1 C0
28) A2 B2 C1
29) A3 B3 C2
30) A4 B4 C3
31) A1 B0 C0
32) A2 B1 C1

, :

if (k % numElements == 0) continue;

, numElements > numSets, Individual Columns . ( , , , , )

Aaannd , n 4 . , , , , . ? ?

+4
4

, , . , , , . , .

, , ( , ), , - . : , . , , . , , , .

, , . . , , , , , . ( , ).

, . , .

class Equidistributed {
  static final double IRRATIONAL1 = Math.sqrt(2);
  static final double IRRATIONAL2 = Math.sqrt(3);
  static final double IRRATIONAL3 = Math.sqrt(5)-1;

  // four sets of 7 elements each
  static int setSize = 7;

  public static void main(String[] args) {
    for (int i = 0; i < Math.pow(setSize,4); i++) {
      String tuple = "";
      int j = i % setSize;
      tuple += j + ",";
      j = ((int)Math.floor(i*IRRATIONAL1)) % setSize;
      tuple += j + ",";
      j = ((int)Math.floor(i*IRRATIONAL2)) % setSize;
      tuple += j + ",";
      j = ((int)Math.floor(i*IRRATIONAL3)) % setSize;
      tuple += j;
      System.out.println(tuple);
    }
  }
}

"" , , . . ( 7). , , ; 1 sqrt (5), 1 2.

(i, floor(i*irrational1), floor(i*irrational2), floor(i*irrational3)) mod 7

, , . , "", . , , , , .

+1

, , . , .

1. (, A1, A34, B4, B32, C5, C40 )

2: A1 .

0

Define an array of all possible combinations. For each possible array order, calculate your distance estimate. If it is larger than the previous one (by default start = 0), copy the array to your output by overwriting the previous best array.

0
source

Generalized algorithm and written code for performance testing:

import java.util.*;

public class Solution {

   public static void main(String[] args) throws Exception {

      List<String> A = new ArrayList<>();
      A.add("A0"); A.add("A1"); A.add("A2"); 
      A.add("A3"); A.add("A4"); A.add("A5"); A.add("A6");

      List<String> B = new ArrayList<>();
      B.add("B0"); B.add("B1"); B.add("B2");
      B.add("B3"); B.add("B4"); B.add("B5"); B.add("B6");

      List<String> C = new ArrayList<>();
      C.add("C0"); C.add("C1"); C.add("C2"); 
      C.add("C3"); C.add("C4"); C.add("C5"); C.add("C6");

      List<String> D = new ArrayList<>();
      D.add("D0"); D.add("D1"); D.add("D2"); 
      D.add("D3"); D.add("D4"); D.add("D5"); D.add("D6");

      List<List<String>> columns = new ArrayList<>();
      columns.add(A); columns.add(B); columns.add(C); columns.add(D);

      List<String> output = equidistribute(columns);

//      for (String row : output) {
//         System.out.println(row);
//      }
//      new Solution().test(output, columns.size(), A.size());

      new Solution().testAllTheThings();

   }

   public static List<String> equidistribute(List<List<String>> columns) {

      List<String> output = new ArrayList<>();

      int[] primeNumbers = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                           43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
                           101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
                           151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
                           199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
                           263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
                           317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
                           383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
                           443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
                           503, 509, 521, 523, 541};

      int numberOfColumns = columns.size();
      int numberOfElements = columns.get(0).size();

      for (int i = 0; i < Math.pow(numberOfElements, numberOfColumns); i++) {

         String row = "";

         for (int j = 0; j < numberOfColumns; j++) {
            if (j==0) {
               row += columns.get(0).get(i % numberOfElements);
            } else {
               int index = ((int) Math.floor(i * Math.sqrt(primeNumbers[j-1]))) % numberOfElements;
               row += " " + columns.get(j).get(index);
            }
         }

         output.add(row);
      }

      return output;
   }

   class MutableInt {
      int value = 0;
      public void increment() { value++; }
      public int get() { return value; }
      public String toString() { return String.valueOf(value); }
   }

   public void test(List<String> columns, int numberOfColumns, int numberOfElements) throws Exception {

      List<HashMap<String, MutableInt>> pairMaps = new ArrayList<>();
      List<HashMap<String, MutableInt>> individualElementMaps = new ArrayList<>();

      // initialize structures for calculating min distance
      for (int i = 0; i < numberOfColumns; i++) {

         if (i != numberOfColumns-1) {
            HashMap<String, MutableInt> pairMap = new HashMap<>();
            pairMaps.add(pairMap);
         }

         HashMap<String, MutableInt> individualElementMap = new HashMap<>();
         individualElementMaps.add(individualElementMap);
      }

      int minDistancePair = Integer.MAX_VALUE;
      int minDistanceElement = Integer.MAX_VALUE;

      String pairOutputMessage = "";
      String pairOutputDebugMessage = "";
      String elementOutputMessage = "";
      String elementOutputDebugMessage = "";
      String outputMessage = numberOfColumns + " columns, " + numberOfElements + " elements";

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

         String[] elements = columns.get(i).split(" ");

         for (int j = 0; j < numberOfColumns; j++) {

            // pair stuff
            if (j != numberOfColumns-1) {

               String pairEntry = elements[j] + " " + elements[j+1];

               MutableInt count = pairMaps.get(j).get(pairEntry);

               if (pairMaps.get(j).containsKey(pairEntry)) {
                  if (count.get() <= minDistancePair) {
                     minDistancePair = count.get();
                     pairOutputMessage = "minDistancePair = " + minDistancePair;
                     pairOutputDebugMessage += "(" + pairEntry + " at line " + (i+1) + ")  min = " + minDistancePair + "\n";
                  }
                  count = null;
               }

               if (count == null) {
                  pairMaps.get(j).put(pairEntry, new MutableInt());
               }
            }

            // element stuff
            String elementEntry = elements[j];

            MutableInt count = individualElementMaps.get(j).get(elementEntry);

            if (individualElementMaps.get(j).containsKey(elementEntry)) {
               if (count.get() <= minDistanceElement) {
                  minDistanceElement = count.get();
                  elementOutputMessage = "minDistanceElement = " + minDistanceElement;
                  elementOutputDebugMessage += "(" + elementEntry + " at line " + (i+1) + ")  min = " + minDistanceElement + "\n";
               }
               count = null;
            }

            if (count == null) {
               individualElementMaps.get(j).put(elementEntry, new MutableInt());
            }

         }

         // increment counters
         for (HashMap<String, MutableInt> pairMap : pairMaps) {
            Iterator it = pairMap.entrySet().iterator();
            while (it.hasNext()) {
               Map.Entry mapEntry = (Map.Entry) it.next();
               ((MutableInt) mapEntry.getValue()).increment();
            }
         }
         for (HashMap<String, MutableInt> elementMap : individualElementMaps) {
            Iterator it = elementMap.entrySet().iterator();
            while (it.hasNext()) {
               Map.Entry mapEntry = (Map.Entry) it.next();
               ((MutableInt) mapEntry.getValue()).increment();
            }
         }

      }

      System.out.println(outputMessage + " -- " + pairOutputMessage + ", " + elementOutputMessage);
//      System.out.print(elementOutputDebugMessage);
//      System.out.print(pairOutputDebugMessage);


   }

   public void testAllTheThings() throws Exception {

      char[] columnPrefix = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".toCharArray();
      int maxNumberOfColumns = columnPrefix.length;
      int maxNumberOfElements = 30;

      for (int i = 2; i < maxNumberOfColumns; i++) {

         for (int j = i; j < maxNumberOfElements; j++) {

            List<List<String>> columns = new ArrayList<>();

            for (int k = 0; k < i; k++) {
               List<String> column = new ArrayList<>();

               for (int l = 0; l < j; l++) {
                  column.add(String.valueOf(columnPrefix[k]) + l);
               }

               columns.add(column);
            }

            List<String> output = equidistribute(columns);
            test(output, i, j);

         }
      }

   }


}

edit: removed the restriction that each set must have the same number of elements

public List<String> equidistribute(List<List<String>> columns) {

  List<String> output = new ArrayList<>();

  int[] primeNumbers = {  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                         43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
                        101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
                        151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
                        199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
                        263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
                        317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
                        383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
                        443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
                        503, 509, 521, 523, 541};

  int numberOfColumns = columns.size();

  int numberOfCombinations = 1;
  for (List<String> column : columns) {
     numberOfCombinations *= column.size();
  }

  for (int i = 0; i < numberOfCombinations; i++) {

     String row = "";

     for (int j = 0; j < numberOfColumns; j++) {

        int numberOfElementsInColumn = columns.get(j).size();

        if (j==0) {
           row += columns.get(0).get(i % numberOfElementsInColumn);
        } else {
           int index = ((int) Math.floor(i * Math.sqrt(primeNumbers[j-1]))) % numberOfElementsInColumn;
           row += "|" + columns.get(j).get(index);
        }
     }

     output.add(row);
  }

  return output;
}
0
source

More articles:


All Articles