Существует ли функция для нахождения всех подгрупп из одной основной группы с фильтрацией некоторых из подгрупп? - PullRequest
Новая
       70

Существует ли функция для нахождения всех подгрупп из одной основной группы с фильтрацией некоторых из подгрупп?

3 голосов
/ 22 января 2020

Я кодирую с java, поэтому, если вы можете поделиться кодом с java, было бы неплохо:)

Допустим, у меня есть группа (1,2,3,4,5) и я хочу создать все подгруппы этой группы с максимальным размером данного натурального числа (например, 3).

Я уже нашел код, который возвращает все подгруппы, однако в моем проекте размер группы может достигать до 40, поэтому мне требуется слишком много времени для расчета и это очень проблематично c. Я также предпочитаю, чтобы это была функция, а не объект. Эффективность также важна, я не могу создать все возможные группы и затем отфильтровать их. 

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<>());
            return sets;
        }
        List<T> list = new ArrayList<>(originalSet);
        T head = list.get(0);
        Set<T> rest = new HashSet<>(list.subList(1, list.size()));
        for (Set<T> set : powerSet(rest)) {
            Set<T> newSet = new HashSet<>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

Я нашел это здесь: Получение набора мощности набора в Java.

Ответы [ 2 ]

2 голосов
/ 28 января 2020

Я видел твой код и немного его подкорректировал.

Теперь вы вводите максимальный размер внутреннего набора, и он будет размером самого большого набора. 

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet, int size) {
        Set<Set<T>> sets = new HashSet<>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<>());
            return sets;
        }
        List<T> list = new ArrayList<>(originalSet);
        T head = list.get(0);
        Set<T> rest = new HashSet<>(list.subList(1, list.size()));
        for (Set<T> set : powerSet(rest, size)) {
            if(set.size() <= size-1 ){
                Set<T> newSet = new HashSet<>();
                newSet.add(head);
                newSet.addAll(set);
                sets.add(newSet);
                sets.add(set);
            }

        }

        return sets;
    }
1 голос
/ 22 января 2020

Я работал над подобными вопросами во время учебы в колледже, вот посмотрите: 

  static Set<String> setA = new HashSet<>();

  public static Set<String> permutation(String prefix, String str, int len) {
    int n = str.length();
    if (prefix.length() == len) {
      setA.add(prefix);
    } else {
      for (int i = 0; i < n; i++) {
        permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), len);
      }
    }
    return setA;
  }

Выше приведено все возможные комбинации String str = 12345 с размером int len=3, теперь ваша работа фильтровать уникальные элементы, потому что 123 равно 312 из Powerset определение. 

  public static void main(String[] args) {
    Set<String> setB = new HashSet<>();
    setB.addAll(permutation("", "12345", 3));
    Set<String> collect = setB.stream().map(
        s -> {
          Optional<String> reduce = Arrays.stream(s.split("")).sorted(Comparator.naturalOrder())
              .reduce((a, b) -> a + b);
          return reduce.get();
        })
        .collect(Collectors.toSet());
    System.out.println(collect);
  }

Это должно работать без каких-либо сомнений, пусть Я знаю, если у вас есть какие-либо сомнения.

Полный код, у меня есть на Github : https://github.com/vishwaratna/Practice-Codes/blob/master/src/main/java/BenchmarkingWithJMH.java

...