Все возможные комбинации массива

Question

У меня есть строковый массив

{"ted", "williams", "golden", "voice", "radio"}

, и я хочу, чтобы все возможные комбинации этих ключевых слов были в следующей форме:

{"ted",
 "williams",
 "golden", 
 "voice", 
 "radio",
 "ted williams", 
 "ted golden", 
 "ted voice", 
 "ted radio", 
 "williams golden",
 "williams voice", 
 "williams radio", 
 "golden voice", 
 "golden radio", 
 "voice radio",
 "ted williams golden", 
 "ted williams voice", 
 "ted williams radio", 
 .... }

Я часами безрезультатнорезультат (побочный эффект высокоуровневого программирования ??).

Я знаю, что решение должно быть очевидным, но я застрял, честно!Решения в Java / C # принимаются.

РЕДАКТИРОВАТЬ :

1. Это не домашнее задание
2. "Тед Уильямс" и "Уильямс Тед"считаются одинаковыми, поэтому я хочу только "ted williams"

EDIT 2 : после просмотра ссылки в ответе выясняется, что пользователи Guava могут использовать метод powersetв com.google.common.collect.Sets

Answer 1

РЕДАКТИРОВАТЬ: Как указали FearUs, лучшим решением является использование Sets.powerset Guava (Set set) .

РЕДАКТИРОВАТЬ 2: Обновлены ссылки.

---

Быстрый и грязный перевод этого решения :

public static void main(String[] args) {

    List<List<String>> powerSet = new LinkedList<List<String>>();

    for (int i = 1; i <= args.length; i++)
        powerSet.addAll(combination(Arrays.asList(args), i));

    System.out.println(powerSet);
}

public static <T> List<List<T>> combination(List<T> values, int size) {

    if (0 == size) {
        return Collections.singletonList(Collections.<T> emptyList());
    }

    if (values.isEmpty()) {
        return Collections.emptyList();
    }

    List<List<T>> combination = new LinkedList<List<T>>();

    T actual = values.iterator().next();

    List<T> subSet = new LinkedList<T>(values);
    subSet.remove(actual);

    List<List<T>> subSetCombination = combination(subSet, size - 1);

    for (List<T> set : subSetCombination) {
        List<T> newSet = new LinkedList<T>(set);
        newSet.add(0, actual);
        combination.add(newSet);
    }

    combination.addAll(combination(subSet, size));

    return combination;
}

Тест:

$ java PowerSet ted williams golden
[[ted], [williams], [golden], [ted, williams], [ted, golden], [williams, golden], [ted, williams, golden]]
$

Answer 2

Я только что столкнулся с этой проблемой и был не очень доволен опубликованными ответами StackExchange, так что вот мой ответ.Это возвращает все комбинации из массива Port объектов.Я предоставлю читателю возможность адаптироваться к любому классу, который вы используете (или сделать его универсальным).

Эта версия не использует рекурсию.

public static Port[][] combinations ( Port[] ports ) {

    List<Port[]> combinationList = new ArrayList<Port[]>();
    // Start i at 1, so that we do not include the empty set in the results
    for ( long i = 1; i < Math.pow(2, ports.length); i++ ) {
        List<Port> portList = new ArrayList<Port>();
        for ( int j = 0; j < ports.length; j++ ) {
            if ( (i & (long) Math.pow(2, j)) > 0 ) {
                // Include j in set
                portList.add(ports[j]);
            }
        }
        combinationList.add(portList.toArray(new Port[0]));
    }
    return combinationList.toArray(new Port[0][0]);
}

Answer 3

Вот подсказка:

All-Subsets(X) = {union for all y in X: All-Subsets(X-y)} union {X}

Answer 4

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

public static <T> T[][] combinations(T[] a) {

    int len = a.length;
    if (len > 31)
        throw new IllegalArgumentException();

    int numCombinations = (1 << len) - 1;

    @SuppressWarnings("unchecked")
    T[][] combinations = (T[][]) java.lang.reflect.Array.newInstance(a.getClass(), numCombinations);

    // Start i at 1, so that we do not include the empty set in the results
    for (int i = 1; i <= numCombinations; i++) {

        @SuppressWarnings("unchecked")
        T[] combination = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
                Integer.bitCount(i));

        for (int j = 0, ofs = 0; j < len; j++)
            if ((i & (1 << j)) > 0)
                combination[ofs++] = a[j];

        combinations[i - 1] = combination;
    }

    return combinations;
}

Answer 5

import java.util.ArrayList;
import java.util.List;
public class AllPossibleCombinations {

public static void main(String[] args) {
    String[] a={"ted", "williams", "golden"};           
    List<List<String>> list = new AllPossibleElementCombinations().getAllCombinations(Arrays.asList(a));
    for (List<String> arr:list) {
        for(String s:arr){
            System.out.print(s);
        }
        System.out.println();
    }
}

public List<List<String>> getAllCombinations(List<String> elements) {
    List<List<String>> combinationList = new ArrayList<List<String>>();
    for ( long i = 1; i < Math.pow(2, elements.size()); i++ ) {
        List<String> list = new ArrayList<String>();
        for ( int j = 0; j < elements.size(); j++ ) {
            if ( (i & (long) Math.pow(2, j)) > 0 ) {
                list.add(elements.get(j));
            }
        }
        combinationList.add(list);
    }
    return combinationList;
}

}

выход:

Ted

Вильямса

tedwilliams

золотой

tedgolden

williamsgolden

tedwilliamsgolden

Answer 6

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

Что я хотел, это было:

Если у меня есть массив с тремя строками

ArrayList<String> tagsArray = new ArrayList<>(Array.asList("foo","bar","cas"));

Я хочу, чтобы все возможные комбинации элементов находились внутри массива:

{"foo","bar","cas","foobar","foocas","barfoo","barcas","casfoo","casbar","foobarcas","casbarfoo","barcasfoo" . . . . . }

Так что для достижения этого результата я реализовал следующий код, используя библиотеку gava в google:

  import static com.google.common.collect.Collections2.orderedPermutations;
  import static java.util.Arrays.asList;

  public void createTags(){

    Set<String> tags =  new HashSet<>();
    tags.addAll(tagsArray);
    Set<Set<String>> tagsSets = Sets.powerSet(tags);

    for (Set<String> sets : tagsSets) {
        List<String> myList = new ArrayList<>();
        myList.addAll(sets);
        if (!myList.isEmpty()) {
            for (List<String> perm : orderedPermutations(myList)) {
                System.out.println(perm);
                String myTag = Joiner.on("").join(perm);
                tagsForQuery.add(myTag);
            }
        }
    }

    for (String hashtag : tagsForQuery) {
        System.out.println(hashtag);
    }
}

Надеюсь, это кому-нибудь поможет, это было не домашнее задание, а приложение для Android.

Answer 7

package rnd;

import java.util.ArrayList;

public class Rnd {
    public static void main(String args[]) {
        String a[] = {"ted", "williams", "golden", "voice", "radio"};
        ArrayList<String> result =new ArrayList<>();
        for(int i =0 ;i< a.length; i++){
            String s = "";
            for(int j =i ; j < a.length; j++){
                s += a[j] + " " ;
                result.add(s);
            }
        }
    }
}