Найти все подмножества длины k в массиве

Ответ 1

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

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

Код 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]]

Ответ 2

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

Ответ 3

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

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 бит не установлены. Теперь, используя эту строку, я нахожу все возможные перестановки этой строки. И затем, используя эти перестановки, я вывожу соответствующий элемент из набора. Было бы здорово, если бы кто-нибудь мог рассказать мне о сложности этой проблемы.

Ответ 4

Это python. Извините за испанский;)

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]))

Ответ 5

   #include<iostream>
   #include<cstdio>
   #include<vector>
   using namespace std;
   vector<int> v;
   vector<vector<int> > result;

  void subset(int arr[],int k,int n,int idx){
  if(idx==n)
 return;

if(k==1){
    for(int i=idx;i<n;i++)
     {
        v.push_back(arr[i]);
        result.push_back(v);
        v.pop_back();
     }
}

 for(int j=idx;j<n;j++) {
  v.push_back(arr[j]);
  subset(arr,k-1,n,j+1);
  v.pop_back();
  }
 }

int main(){
int arr[] = {1,2,3,4,5,6,7};
int k = 4;
int n =sizeof(arr)/sizeof(arr[0]);
subset(arr,k,n,0);

for(int i = 0;i<result.size();i++)
 { 
  for(int j = 0;j<result[i].size();j++)
   {
     cout << result[i][j] << " ";
   }
   cout << endl;
 }
}

Ответ 6

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

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));
    }
}

Ответ 7

Это реализация в 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

Ответ 8

Выполнение 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));

Ответ 9

Вот итеративная версия в 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

Ответ 10

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

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;
}

Ответ 11

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

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;
                }
            };
        }
    };
}

Ответ 12

Еще одно интересное решение.

#include<bits/stdc++.h>
using namespace std;
long factorial(int n) { return (n==1|| n==0|| n < 0) ? 1 : n *factorial(n-1) ;}
void printS(int set[],int n,int k) 
{ 

   long noofsubset =  factorial(n) / (factorial(n-k)*factorial(k));
   bitset<32> z ((1 << (k)) - 1);
   string s = z.to_string();
    int i = 0;
        while(i<noofsubset)
        { 
                  for (int j = 0; j  < n;j++)
                  {
                      if(s[(32-n)+j] == '1')
                        cout << set[j]<<" ";
                  }
                    cout << endl;
                next_permutation(s.begin(),s.end());
                i++;
        } 
}

void printSubsetsOfArray(int input[], int size) {
    int k  = 3;
  printS(input,size,k)  ;
}