Générer des combinaisons ordonnées par un attribut

https://stackoverflow.com/questions/523800

22-08-2019
|

Question

Je cherche un moyen de générer des combinaisons d'objets commandés par un seul attribut. Je ne pense pas que l'ordre lexicographique est ce que je cherche ... Je vais essayer de donner un exemple. Disons que j'ai une liste d'objets A, B, C, D avec les valeurs d'attribut que je veux commander en étant 3,3,2,1. Cela donne A3, B3, C2, D1 objets. Maintenant, je veux générer des combinaisons de 2 objets, mais ils doivent être commandés de manière descendante:

A3 B3
A3 C2
B3 C2
A3 D1
B3 D1
C2 D1

Génération toutes les combinaisons et les tri n'est pas acceptable parce que le scénario du monde réel implique de grands ensembles et des millions de combinaisons. (Ensemble de 40, ordre de 8), et j'ai besoin que des combinaisons au-dessus du seuil.

En fait, je besoin compte des combinaisons ci-dessus d'un seuil groupés par une somme d'un attribut donné, mais je pense qu'il est beaucoup plus difficile à faire - donc je me contenterais pour développer toutes les combinaisons supérieures à un seuil et les compter. Si cela est possible du tout.

EDIT - Ma question originale n'a pas été très précis ... Je ne dois pas vraiment ces combinaisons ordonné, juste pensé qu'il serait utile d'isoler des combinaisons supérieures à un seuil. Pour être plus précis, dans l'exemple ci-dessus, ce qui donne un seuil de 5, je cherche une information que l'ensemble donné produit une combinaison avec un total de six (A3 B3) et deux avec un total de cinq (A3 C2, B3 C2). Je ne suis pas vraiment besoin des combinaisons elles-mêmes.

Je regardais en somme problème sous-ensemble, mais si je comprends bien la solution dynamique étant donné qu'il ne vous donne l'information est-il une somme donnée ou non, pas compte des sommes.

Merci

La solution

En fait, je pense que vous ne veux ordre lexicographique, mais descendant plutôt que par ordre croissant. En outre:

Il est pas clair pour moi de votre description A, B, D ... jouer un rôle dans votre réponse (sauf peut-être que le conteneur pour les valeurs).
Je pense que votre exemple de question est simplement « Pour chaque entier au moins 5, jusqu'à total maximum de deux valeurs, combien de paires distinctes de l'ensemble {3, 3, 2, 1} ont des sommes de cet entier? «
La partie intéressante est le début de sauvetage, une fois aucune solution possible peut être atteinte (RESTANT sommes réalisables sont trop petites).

~~Je posterai exemple de code plus tard.~~

Voici le code exemple je l'ai promis, avec quelques remarques suivantes:

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

Préface Remarques:

Il utilise une petite classe d'aide appelée Tally, qui vient d'isoler le tableau (y compris l'initialisation des clés encore jamais vu). Je vais le mettre à la fin.

Pour conserver ce concise, j'ai pris quelques raccourcis qui ne sont pas bonnes pratiques pour le code « réel »:

Cela ne vérifie pas pour un tableau de valeur nulle, etc.
Je suppose que le tableau de valeur est déjà triée dans l'ordre décroissant, requis pour la technique précoce renflouement. (Code de bonne production comprendrait le tri.)
Je mets des données transitoires dans les variables d'instance au lieu de les passer comme arguments parmi les méthodes privées qui prennent en charge count. Cela rend cette classe non-thread-safe.

Explication:

Une instance de Combos est créé avec le (descendant commandé) tableau d'entiers à combiner. Le tableau de value est mis en place une fois par exemple, mais plusieurs appels à count peut être fait avec différentes tailles et limites population.

La méthode count déclenche une (la plupart du temps) traversal récursive standard combinaisons uniques de nombres entiers n de values. L'argument limit donne la limite inférieure des sommes d'intérêt.

La méthode countAt examine les combinaisons de nombres entiers de values. L'argument est left combien entiers restent pour compenser entiers n en somme, start est la position dans values à partir de laquelle la recherche et sum est la somme partielle.

Le mécanisme en début de sauvetage est basé sur le calcul best, un tableau à deux dimensions qui indique la somme « meilleur » accessible à partir d'un état donné. La valeur de best[n][p] est la plus grande somme des valeurs de n commence à p de position du values d'origine.

Le récursivité des fonds de countAt lorsque la population correcte a été accumulée; cela ajoute la sum actuelle (des valeurs de n) au tally. Si countAt n'a pas touché le fond, il balaye la values de la position de start-tion pour augmenter le sum courant partiel, aussi longtemps que:

positions assez restent values pour atteindre la population spécifiée, et
le best (le plus grand) Sous-total restant est assez grand pour faire le limit.

Une série d'échantillons avec les données de votre question:

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

produit les résultats que vous avez spécifié:

found 2 sums of 5
found 1 sums of 6

Voici le code Tally:

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}

Autres conseils

J'ai écrit une classe pour gérer des fonctions communes pour travailler avec le coefficient binomial, qui est le type de problème que votre problème relève. Il effectue les tâches suivantes:

Sorties tous les indices K dans un format agréable pour tout N choisir K dans un fichier. Les K-indices peuvent être substitués par des chaînes plus descriptives ou des lettres. Cette méthode permet de résoudre ce type de problème tout à fait banal.
convertit les K index à l'index approprié d'une entrée dans la table de coefficient binomial triée. Cette technique est beaucoup plus rapide que les techniques publiées anciennes qui se fondent sur l'itération. Il le fait en utilisant une propriété mathématique inhérente au triangle de Pascal. Mon papier parle à ce sujet. Je crois que je suis le premier à découvrir et publier cette technique, mais je peux me tromper.
Convertit l'index dans une table de coefficient binomial triée pour les K-indices correspondants.
Utilise méthode de Mark Dominus pour calculer le coefficient binomial, ce qui est beaucoup moins susceptibles de déborder et travaille avec un plus grand nombre.

La classe est écrit dans # .NET C et fournit un moyen de gérer les objets liés au problème (le cas échéant) à l'aide d'une liste générique. Le constructeur de cette classe prend une valeur bool appelée InitTable que lorsque true créer une liste générique pour contenir les objets à gérer. Si cette valeur est fausse, il ne crée pas la table. Le tableau n'a pas besoin d'être créé afin d'effectuer les 4 méthodes ci-dessus. Les méthodes d'accès sont prévus pour accéder à la table.

Il y a une classe de test associé qui montre comment utiliser la classe et ses méthodes. Il a été testé avec 2 cas et il n'y a pas de bugs connus.

Pour en savoir plus sur cette classe et télécharger le code, voir Tablizing Le binomiale Coeffieicent .

Consultez cette question stackoverflow: algorithme retour toutes les combinaisons s

Je viens aussi utilisé un code java ci-dessous pour générer toutes les permutations, mais il pourrait facilement être utilisé pour générer donné un indice de combinaison unique.

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}

Je suis désolé (après toutes ces précisions dans les commentaires) de dire que je ne pouvais pas trouver une solution efficace à ce problème. J'ai essayé pendant la dernière heure sans résultat.

La raison (je pense) est que ce problème est très similaire à des problèmes tels que le problème du voyageur de commerce. Jusqu'à ce que, sauf si vous essayez toutes les combinaisons, il n'y a aucun moyen de savoir quels attributs ajouter jusqu'à le seuil.

Il semble y avoir aucune astuce qui peut résoudre cette classe de problèmes.

Pourtant, il y a de nombreuses optimisations que vous pouvez faire pour le code réel.

Essayer de trier les données selon les attributs. Vous pouvez être en mesure d'éviter le traitement de certaines valeurs de la liste lorsque vous constatez qu'une valeur supérieure ne peut pas satisfaire le seuil (donc toutes les valeurs inférieures peuvent être éliminés).

Si vous utilisez C # il y a une assez bonne bibliothèque . Notez bien que la génération de certaines permutations ne sont pas dans l'ordre lexicographique

Voici une approche récursive nombre le nombre de ces sous-ensembles: Nous définissons une count(minIndex,numElements,minSum) fonction qui renvoie le nombre de sous-ensembles de taille numElements dont la somme est au moins minSum, contenant des éléments avec des indices minIndex ou plus .

Comme dans l'énoncé du problème, nous trions nos éléments dans l'ordre décroissant, par exemple [3,3,2,1], et appeler le premier indice zéro, et le nombre total d'éléments N. Nous supposons que tous les éléments sont non négatifs. Pour l'ensemble des 2 sous-ensembles dont la somme est d'au moins 5, nous appelons count(0,2,5).

Exemple de code (Java):

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

BTW, j'ai couru ci-dessus avec un tableau de 40 éléments et taille-8 sous-ensembles et constamment obtenu des résultats en moins de retour d'une seconde.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow