Как создать набор мощности данного списка?

Ответ 1

То, что вы ищете, по существу, это power set (минус, возможно, пустой набор). У Guava есть метод для этого: Sets.powerSet(). Вы можете просмотреть источник класса Sets, чтобы узнать, как этот метод реализован, если вы хотите написать его самостоятельно; вам может потребоваться изменить его, чтобы вернуть List вместо Set, так как вы хотите сохранить порядок, хотя это изменение не должно быть слишком резким. После того, как у вас есть установленная мощность, это должно быть тривиально, чтобы перебрать его и построить нужную карту.

Ответ 2

То, что вы спрашиваете, порождает все возможные подмножества набора. Вы можете думать об этом как итерации по всем возможным бинарным массивам размера N (размер вашего списка):

000000...000
000000...001
000000...010
000000...011
etc.

Почему? Ответ прост: 1 указывает, что элемент существует в подмножестве, а 0 указывает, что он отсутствует.

Итак, основной алгоритм очевиден:

s = [A, B, C, D]

for i=0 to 2^N-1:
   b = convert_number_to_bin_array(i)
   ss = calculate_subset_based_on_bin_array(s, b)
   print ss

Где calculate_subset_based_on_bin_array выполняет итерацию на b и s и выбирает элементы из s[current], где b[current] = 1.

Вышеприведённое будет распечатывать все существующие подмножества. Вы можете адаптировать этот алгоритм, чтобы получить карту, о которой вы просили в своем вопросе.

Ответ 3

static Map<Integer, List<LinkedList<Integer>>> powerset = new HashMap<>();

public static void main(String[] args) throws IOException {
    powerset(Arrays.asList(1, 2, 3));
    for (Integer key : powerset.keySet()) {
        System.out.print(key + " -> ");
        System.out.println(Arrays.toString(powerset.get(key).toArray()));
    }
}

static void powerset(List<Integer> src) {
    powerset(new LinkedList<>(), src);
}

private static void powerset(LinkedList<Integer> prefix, List<Integer> src) {
    if (src.size() > 0) {
        prefix = new LinkedList<>(prefix); //create a copy to not modify the orig
        src = new LinkedList<>(src); //copy
        Integer curr = src.remove(0);
        collectResult(prefix, curr);
        powerset(prefix, src);
        prefix.add(curr);
        powerset(prefix, src);
    }
}

private static void collectResult(LinkedList<Integer> prefix, Integer curr) {
    prefix = new LinkedList<>(prefix); //copy
    prefix.add(curr);
    List<LinkedList<Integer>> addTo;
    if (powerset.get(prefix.size()) == null) {
        List<LinkedList<Integer>> newList = new LinkedList<>();
        addTo = newList;
    } else {
        addTo = powerset.get(prefix.size());
    }
    addTo.add(prefix);
    powerset.put(prefix.size(), addTo);
}

OUTPUT

1 -> [[1], [2], [3]]
2 -> [[2, 3], [1, 2], [1, 3]]
3 -> [[1, 2, 3]]

Ответ 4

Вот код, который я тестировал для создания всех возможных комбинаций из заданного массива:

enter code here
import java.util.Arrays;

public class PasswordGen {
static String[] options = { "a", "b", "c", "d" };
static String[] places = new String[options.length];
static int count;

public static void main(String[] args) {
    // Starting with initial position of a i.e. 0
    sequence(0, places.clone());
}

private static void sequence(int level, String[] holder) {
    if (level >= options.length) {
        // combination complete
        System.out.println("" + (++count) + " Combination "
                + Arrays.toString(holder));
        return;
    }

    String val = options[level];
    String[] inrHolder = null;
    for (int c = 0; c < holder.length; c++) {
        inrHolder = holder.clone();
        if (inrHolder[c] == null) {
            inrHolder[c] = val;
            sequence(level + 1, inrHolder.clone());
        }
    }
    return;
}
}

Ответ 5

Существует несколько способов решения этой проблемы, но самым простым способом является ИМХО - использовать рекурсию. Ниже я предоставил итеративный и рекурсивный подход к решению проблемы генерации всех комбинаций множества. Общая идея обоих подходов состоит в том, чтобы сгенерировать набор индексов, принадлежащих элементам, которые вы хотите выбрать.

Для рекурсивного подхода вы хотите отслеживать три части информации: логический массив, указывающий, был ли выбран элемент или нет, позиция, в которой вы находитесь, в своем списке элементов и переменную r, отслеживающую количество элементы, оставшиеся для выбора. Затем до тех пор, пока r!= 0 (это означает, что вам все равно нужно выбрать r элементов для завершения этой комбинации), вы возвращаетесь к выбору элемента, который вы еще не выбрали, и перемещаетесь вперед в массиве.

Код, показанный ниже, был взят из моего github repo.

/**
 * Here we present two methods (recursive and iterative) of generating all
 * the combinations of a set by choosing only r of n elements.
 * 
 * Time Complexity: O( n choose r )
 *
 * @author William Fiset, Micah Stairs
 **/

public class Combinations {

  // This method finds all the combinations of size r in a set
  public static void combinationsChooseR(int[] set, int r) {

    if (r < 0) return;
    if (set == null) return;

    boolean [] used = new boolean[set.length];
    combinations(set, r, 0, used);

  }

  // To find all the combinations of size r we need to recurse until we have
  // selected r elements (aka r = 0), otherwise if r != 0 then we need to select
  // an element which is found after the position of our last selected element
  private static void combinations(int[] set, int r, int at, boolean[] used) {

    final int N = set.length;

    // If there are more elements left to select than what are available
    // This is a short circuiting optimization we can take advantage of 
    int elementsLeftToPick = N - at;
    if (elementsLeftToPick < r) return;

    // We selected 'r' elements so we found a valid subset!
    if (r == 0) {

      System.out.print("{ ");
      for (int i = 0; i < N; i++)
        if (used[i])
          System.out.print(set[i] + " ");
      System.out.println("}");

    } else {

      for (int i = at; i < N; i++) {

        // Try including this element
        used[i] = true;
        combinations(set, r - 1, i + 1, used);

        // Backtrack and try the instance where we did not include this element
        used[i] = false;

      }

    }

  }

  // Use this method in combination with a do while loop to generate all the 
  // combinations of a set choose r in a iterative fashion. This method returns
  // false once the last combination has been generated.
  // NOTE: Originally the selection needs to be initialized to {0,1,2,3 ... r-1}
  public static boolean nextCombination(int[] selection, int N, int r) {
    if (r > N) throw new IllegalArgumentException("r must be <= N");
    int i = r - 1;
    while (selection[i] == N - r + i)
      if (--i < 0) return false;
    selection[i]++;
    for (int j = i + 1; j < r; j++) selection[j] = selection[i] + j - i;
    return true;
  }

  public static void main(String[] args) {

    // Recursive approach
    int R = 3;
    int[] set = {1,2,3,4,5};
    combinationsChooseR(set, R);
    // prints:
    // { 1 2 3 }
    // { 1 2 4 }
    // { 1 2 5 }
    // { 1 3 4 }
    // { 1 3 5 }
    // { 1 4 5 }
    // { 2 3 4 }
    // { 2 3 5 }
    // { 2 4 5 }
    // { 3 4 5 }      

    // Suppose we want to select all combinations of colors where R = 3
    String[] colors = {"red", "purple", "green", "yellow", "blue", "pink"};
    R = 3;

    // Initialize the selection to be {0, 1, ... , R-1}
    int[] selection = { 0, 1, 2 };
    do {

      // Print each combination
      for (int index : selection)
        System.out.print(colors[index] + " ");
      System.out.println();

    } while( nextCombination(selection, colors.length, R) );
    // prints:
    // red purple green 
    // red purple yellow 
    // red purple blue 
    // red purple pink 
    // red green yellow 
    // red green blue 
    // red green pink 
    // red yellow blue 
    // red yellow pink 
    // red blue pink 
    // purple green yellow 
    // purple green blue 
    // purple green pink 
    // purple yellow blue 
    // purple yellow pink 
    // purple blue pink 
    // green yellow blue 
    // green yellow pink 
    // green blue pink 
    // yellow blue pink    

  }

}

Ответ 6

Я тестирую код, предложенный Elist, и я обнаружил ошибки.

Вот предлагаемая поправка: (в последнем случае функции getPermutation() я сделал два изменения)

public class OrderedPowerSet<E> {
private ArrayList<E> inputList;
public int N;
private Map<Integer, List<Set<E>>> map = 
        new HashMap<Integer, List<Set<E>>>();

public OrderedPowerSet(ArrayList<E> list) {
    inputList = list;
    N = list.size();
}

public List<Set<E>> getPermutationsList(int elementCount) {
    if (elementCount < 1 || elementCount > N) {
        throw new IndexOutOfBoundsException(
                "Can only generate permutations for a count between 1 to " + N);
    }
    if (map.containsKey(elementCount)) {
        return map.get(elementCount);
    }

    ArrayList<Set<E>> list = new ArrayList<Set<E>>();

    if (elementCount == N) {
        list.add(new HashSet<E>(inputList));
    } else if (elementCount == 1) {
        for (int i = 0 ; i < N ; i++) {
            Set<E> set = new HashSet<E>();
            set.add(inputList.get(i));
            list.add(set);
        }
    } else {
        for (int i = 0 ; i < N-elementCount ; i++) {
            @SuppressWarnings("unchecked")
            ArrayList<E> subList = (ArrayList<E>)inputList.clone(); // one change
            subList.remove(0);
            OrderedPowerSet<E> subPowerSet = 
                    new OrderedPowerSet<E>(subList);
            for (Set<E> s : subPowerSet.getPermutationsList(elementCount-1)) {
                Set<E> set = new HashSet<E>();
                set.add(inputList.get(i));
                set.addAll(s);
                list.add(set); // second change
            }

        }
    }

    map.put(elementCount, list);

    return map.get(elementCount);
}

}

Ответ 7

public static List<String> getCombinationsLists(List<String> elements)
{

    //return list with empty String
    if(elements.size() == 0){
        List<String> allLists = new ArrayList<String>();
        allLists.add("");
        return allLists ;
    }

    String first_ele = elements.remove(0);
    List<String> rest = getCobminationLists(elements);
    int restsize = rest.size();
    //Mapping the first_ele with each of the rest of the elements.
    for (int i = 0; i < restsize; i++) {
        String ele = first_ele + rest.get(i);
        rest.add(ele);
    }

    return   rest;
}

Этот набор мощности является одним из упражнений в книге SICP "Структура и интерпретация компьютерного программирования". Каждый программист должен ее прочитать.

Ответ 8

ОП решение перешло от вопроса к ответу:

Благодаря предыдущим ответам я придумал следующую реализацию:

public class OrderedPowerSet<E> {
    private static final int ELEMENT_LIMIT = 12;
    private List<E> inputList;
    public int N;
    private Map<Integer, List<LinkedHashSet<E>>> map = 
            new HashMap<Integer, List<LinkedHashSet<E>>>();

    public OrderedPowerSet(List<E> list) {
        inputList = list;
        N = list.size();
        if (N > ELEMENT_LIMIT) {
            throw new RuntimeException(
                    "List with more then " + ELEMENT_LIMIT + " elements is too long...");
        }
    }

    public List<LinkedHashSet<E>> getPermutationsList(int elementCount) {
        if (elementCount < 1 || elementCount > N) {
            throw new IndexOutOfBoundsException(
                    "Can only generate permutations for a count between 1 to " + N);
        }
        if (map.containsKey(elementCount)) {
            return map.get(elementCount);
        }

        ArrayList<LinkedHashSet<E>> list = new ArrayList<LinkedHashSet<E>>();

        if (elementCount == N) {
            list.add(new LinkedHashSet<E>(inputList));
        } else if (elementCount == 1) {
            for (int i = 0 ; i < N ; i++) {
                LinkedHashSet<E> set = new LinkedHashSet<E>();
                set.add(inputList.get(i));
                list.add(set);
            }
        } else {
            list = new ArrayList<LinkedHashSet<E>>();
            for (int i = 0 ; i <= N - elementCount ; i++) {
                @SuppressWarnings("unchecked")
                ArrayList<E> subList = (ArrayList<E>)((ArrayList<E>)inputList).clone();
                for (int j = i ; j >= 0 ; j--) {
                    subList.remove(j);
                }
                OrderedPowerSet<E> subPowerSet = 
                        new OrderedPowerSet<E>(subList);

                List<LinkedHashSet<E>> pList = 
                        subPowerSet.getPermutationsList(elementCount-1);
                for (LinkedHashSet<E> s : pList) {
                    LinkedHashSet<E> set = new LinkedHashSet<E>();
                    set.add(inputList.get(i));
                    set.addAll(s);
                    list.add(set);
                }               
            }
        }

        map.put(elementCount, list);

        return map.get(elementCount);
    }
}