Вопрос по algorithm, arrays, set, permutation – Найти все подмножества длины k в массиве

25

Учитывая набор{1,2,3,4,5...n} из n элементов нам нужно найти все подмножества длины k.

Например, если n = 4 и k = 2,output было бы{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

Я даже не могу понять, как начать. Нам не нужно использовать встроенные библиотечные функции, такие как next_permutation и т. Д.

Нужен алгоритм и реализация на C / C ++ или Java.

Пожалуйста, посмотрите другую ветку с тем же вопросом и альтернативный метод решения:stackoverflow.com/questions/127704/… (может быть легко преобразован из C # в Java) jacoblambert

Ваш Ответ

10   ответов
0

Если вы ищете ответ шаблона Итератор, то здесь вы идете.

public static <T> Iterable<List<T>> getList(final Iterable<? extends T> list) {

    List<List<T>> listOfList = new ArrayList<>();

    for (T t: list)
        listOfList.add(Collections.singletonList(t));

    return listOfList;
}
public static <T> Iterable<List<T>> getIterable(final Iterable<? extends T> list, final int size) {

    final List<T> vals = new ArrayList<>();
    int numElements = 0;
    for (T t : list) {
        vals.add(t);
        numElements++;
    }

    if (size == 1) {
        return getList(vals);
    }
    if (size == numElements) {
        return Collections.singletonList(vals);
    }

    return new Iterable<List<T>>() {

        @Override
        public Iterator<List<T>> iterator() {
            return new Iterator<List<T>>() {

                int currPos = 0;                    
                Iterator<List<T>> nextIterator = getIterable(
                    vals.subList(this.currPos + 1, vals.size()), size - 1).iterator();

                @Override
                public boolean hasNext() {
                    if ((this.currPos < vals.size()-2) && (this.currPos+size < vals.size()))
                        return true;
                    return false;
                }

                @Override
                public List<T> next() {
                    if (!nextIterator.hasNext()) {
                        this.currPos++;
                        nextIterator = getIterable(vals.subList(this.currPos+1, vals.size()), size-1).iterator();
                    }
                    final List<T> ret = new ArrayList<>(nextIterator.next());
                    ret.add(0, vals.get(this.currPos));
                    return ret;
                }
            };
        }
    };
}
1

Это питон. Простите за испанский;)

from pprint import pprint
conjunto = [1,2,3,4, 5,6,7,8,9,10]
k = 3
lista = []
iteraciones = [0]
def subconjuntos(l, k):
    if k == len(l):
        if not l in lista:
            lista.append(l)
        return
    for i in l:
        aux = l[:]
        aux.remove(i)
        result = subconjuntos(aux, k)
        iteraciones[0] += 1
        if not result in lista and result:
            lista.append( result)

subconjuntos(conjunto, k)
print (lista)
print ('cant iteraciones: ' + str(iteraciones[0]))
0

Это реализация в F #:

// allSubsets: int -> int -> Set<Set<int>>
let rec allSubsets n k =
    match n, k with
    | _, 0 -> Set.empty.Add(Set.empty)
    | 0, _ -> Set.empty
    | n, k -> Set.union (Set.map (fun s -> Set.add n s) (allSubsets (n-1) (k-1)))
                        (allSubsets (n-1) k)

Вы можете попробовать это в F # REPL:

> allSubsets 3 2;;

val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [2; 3]]

> allSubsets 4 2;;

val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [1; 4]; set [2; 3]; set [2; 4]; set [3; 4]]

Этот класс Java реализует тот же алгоритм:

import java.util.HashSet;
import java.util.Set;

public class AllSubsets {

    public static Set<Set<Integer>> allSubsets(int setSize, int subsetSize) {
        if (subsetSize == 0) {
            HashSet<Set<Integer>> result = new HashSet<>();
            result.add(new HashSet<>());
            return result;
        }
        if (setSize == 0) {
            return new HashSet<>();
        }
        Set<Set<Integer>> sets1 = allSubsets((setSize - 1), (subsetSize - 1));
        for (Set<Integer> set : sets1) {
            set.add(setSize);
        }
        Set<Set<Integer>> sets2 = allSubsets((setSize - 1), subsetSize);
        sets1.addAll(sets2);
        return sets1;
    }
}

Если вам не нравится F # или Java, посетите этот сайт. В нем перечислены решения вашей конкретной проблемы на разных языках программирования:

http://rosettacode.org/wiki/Combinations

0

Вот Java-версия того, о чем, я думаю, говорит Simple, используя двоичное представление всех наборов в наборе мощности. Это похоже на то, как это делал Abhiroop Sarkar, но я думаю, что логический массив имеет больше смысла, чем строка, когда вы просто представляете двоичные значения.

private ArrayList<ArrayList<Object>> getSubsets(int m, Object[] objects){
    // m = size of subset, objects = superset of objects
    ArrayList<ArrayList<Object>> subsets = new ArrayList<>();
    ArrayList<Integer> pot = new ArrayList<>();
    int n = objects.length;
    int p = 1;
    if(m==0)
        return subsets;
    for(int i=0; i<=n; i++){
        pot.add(p);
        p*=2;
    }
    for(int i=1; i<p; i++){
        boolean[] binArray = new boolean[n];
        Arrays.fill(binArray, false);
        int y = i;
        int sum = 0;
        for(int j = n-1; j>=0; j--){
            int currentPot = pot.get(j);
            if(y >= currentPot){
                binArray[j] = true;
                y -= currentPot;
                sum++;
            }
            if(y<=0)
                break;
        }
        if(sum==m){
            ArrayList<Object> subsubset = new ArrayList<>();
            for(int j=0; j < n; j++){
                if(binArray[j]){
                    subsubset.add(objects[j]);
                }
            }
            subsets.add(subsubset);
        }
    }

    return subsets;
}
Спасибо, но в этом есть ошибки. Для m == 0 или m == n должна быть возвращена одна запись, содержащая исходный список. Вы можете добавить это в качестве проверки в начале. Ваша версия фактически возвращает 2 ^ n копий исходного списка, если m == n. Также чек на m & gt; п хорошая идея. Фиксированная версия здесь:tinybrain.de/1010466
40

Рекурсия твой друг для этой задачи.

Для каждого элемента - «угадай» если он находится в текущем подмножестве и рекурсивно вызывается с помощью предположения и меньшего надмножества, из которого вы можете выбрать. Это можно сделать как для «да» и "нет" догадки - приведут ко всем возможным подмножествам.
Ограничение себя до определенной длины может быть легко сделано в пункте «стоп».

Java-код:

private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
    //successful stop clause
    if (current.size() == k) {
        solution.add(new HashSet<>(current));
        return;
    }
    //unseccessful stop clause
    if (idx == superSet.size()) return;
    Integer x = superSet.get(idx);
    current.add(x);
    //"guess" x is in the subset
    getSubsets(superSet, k, idx+1, current, solution);
    current.remove(x);
    //"guess" x is not in the subset
    getSubsets(superSet, k, idx+1, current, solution);
}

public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
    List<Set<Integer>> res = new ArrayList<>();
    getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
    return res;
}

Вызов с:

List<Integer> superSet = new ArrayList<>();
superSet.add(1);
superSet.add(2);
superSet.add(3);
superSet.add(4);
System.out.println(getSubsets(superSet,2));

Даст:

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
@Nimrod Этот ответ предназначен для & quot; наборов & quot; (неупорядоченный). По сути, вам нужно отслеживать элементы, которые вы использовали (чтобы не допустить многократного использования) - и в & quot; угадать & quot; шаг, у вас есть больше, чем & quot; использовать & quot; и «не использовать»; Параметры, вам нужно перебрать все неиспользуемые значения.
@sTEAK .: Существует экспоненциальное количество подмножеств, поэтому боюсь, что эффективность - это не вариант. Удачи!
@AdarHefer Нет, он экспоненциальный по k, который является входным, а не постоянным. Так что п ^ к определенно не полиномиален.
Для заданных n и k (что является проблемой) существует полиномиальное количество подмножеств, примерно O (n ^ k).
Спасибо, это делает. Я тоже имел это в виду. Но я искал что-то эффективное. h4ck3d
0

Реализация JavaScript:

var subsetArray = (function() {
  return {
    getResult: getResult
  }

  function getResult(array, n) {

    function isBigEnough(value) {
      return value.length === n;
    }

    var ps = [
      []
    ];
    for (var i = 0; i < array.length; i++) {
      for (var j = 0, len = ps.length; j < len; j++) {
        ps.push(ps[j].concat(array[i]));
      }
    }
    return ps.filter(isBigEnough);
  }
})();



 var arr = [1, 2, 3, 4,5,6,7,8,9];
 console.log(subsetArray.getResult(arr,2));
0

Вот итерационная версия в Python. Суть этого - функция increment_counters (), которая возвращает все возможные комбинации. Мы знаем, что это нужно вызывать C (n, r) раз.

def nchooser(n,r):
    """Calculate the n choose r manual way"""
    import math
    f = math.factorial
    return f(n) / f(n-r) / f(r)

def increment_counters(rc,r,n):
    """This is the essense of the algorithm. It generates all possible indexes.
    Ex: for n = 4, r = 2, rc will have values (0,1),(0,2),(0,3),(1,2),(1,3),(2,3).
    You may have better understanding if you print all possible 35 values for
    n = 7, r = 3."""

    rc[r-1] += 1     # first increment the least significant counter
    if rc[r-1] < n:  # if it does not overflow, return
        return

    # overflow at the last counter may cause some of previous counters to overflow
    # find where it stops (ex: in n=7,r=3 case, 1,2,3 will follow 0,5,6)
    for i in range(r-2,-1,-1): # from r-2 to 0 inclusive
        if rc[i] < i+n-r:
            break
    # we found that rc[i] will not overflow. So, increment it and reset the
    # counters right to it. 
    rc[i] += 1
    for j in range(i+1,r):
        rc[j] = rc[j-1] + 1

def combinations(lst, r):
    """Return all different sub-lists of size r"""
    n = len(lst)
    rc = [ i for i in range(r) ]  # initialize counters
    res = []
    for i in range(nchooser(n,r)): # increment the counters max possible times 
        res.append(tuple(map(lambda k: lst[k],rc)))
        increment_counters(rc,r,n)

    return res
0

Пожалуйста, проверьте мое решение: -

private static void printPermutations(List<Integer> list, int subSetSize) {
    List<Integer> prefixList = new ArrayList<Integer>();
    printPermutations(prefixList, list, subSetSize);
}

private static void printPermutations(List<Integer> prefixList, List<Integer> list, int subSetSize) {
    if (prefixList.size() == subSetSize) {
        System.out.println(prefixList);
    } else {
        for (int i = 0; i < list.size(); i++) {
            Integer removed = list.remove(i);
            prefixList.add(removed);
            printPermutations(prefixList, list, subSetSize);
            prefixList.remove(removed);
            list.add(i, removed);
        }
    }
}

Это похоже на перестановки строк:

private static void printPermutations(String str) {
    printAllPermutations("", str);
}

private static void printAllPermutations(String prefix, String restOfTheString) {
    int len = restOfTheString.length();
    System.out.println(prefix);
    for (int i = 0; i < len; i++) {
        printAllPermutations(prefix + restOfTheString.charAt(i), restOfTheString.substring(0, i) + restOfTheString.substring(i + 1, len));
    }
}
Было бы неплохо, если бы вы добавили пояснения о том, что вы сделали и почему
@UriAgassi Вы можете сейчас следовать решению?
Устное объяснение намного лучше, чем больше кода ... Вы нашли время, чтобы ответить на старый вопрос - дайте нам понимание того, насколько ваш ответ лучше, чем остальные.
1

Проверьте мое решение

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


 public class Subset_K {
public static void main(String[]args)
{
    Set<String> x;
    int n=4;
    int k=2;
    int arr[]={1,2,3,4};
    StringBuilder sb=new StringBuilder();
    for(int i=1;i<=(n-k);i++)
        sb.append("0");
    for(int i=1;i<=k;i++)
        sb.append("1");
    String bin=sb.toString();
    x=generatePerm(bin);
    Set<ArrayList <Integer>> outer=new HashSet<ArrayList <Integer>>();
    for(String s:x){
        int dec=Integer.parseInt(s,2);
        ArrayList<Integer> inner=new ArrayList<Integer>();
        for(int j=0;j<n;j++){
            if((dec&(1<<j))>0)
                inner.add(arr[j]);
        }
        outer.add(inner);
    }
    for(ArrayList<?> z:outer){
        System.out.println(z);
    }
}

    public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}
}

Я работаю над набором из 4 элементов для целей тестирования и использую k = 2. Я пытаюсь сначала создать двоичную строку, в которой установлены k битов, а n-k битов не установлены. Теперь, используя эту строку, я нахожу все возможные перестановки этой строки. И затем, используя эти перестановки, я выводю соответствующий элемент в наборе. Было бы здорово, если бы кто-то мог рассказать мне о сложности этой проблемы.

3

Используйте представление набора битовых векторов и используйте алгоритм, аналогичный тому, что делает std :: next_permutation в 0000.1111 (n-k нулей, k единиц). Каждая перестановка соответствует подмножеству размера k.

Пожалуйста, объясните больше ...
Его ответ очень хороший, но вы правы @NickBailey - недостаточно подробностей. Я реализовал это в другой теме (но до сих пор не видел эту тему)stackoverflow.com/questions/127704/…
Это исключительно бесполезный ответ. Он не имеет достаточно информации, чтобы кто-то мог реализовать алгоритм, который вы набросали.

Похожие вопросы