Trouver des permutations uniques pour l'objet

Question

J'ai une liste de produits qui ont un ID et une quantité, et j'ai besoin de trouver une liste de combinaisons de produits qui rempliront une certaine quantité.

E.g.

ProductID | Quantity 
1   | 5 
2   | 5 
3   | 8 
4   | 15 

Si je requiers une quantité de 15 alors je veux obtenir une liste avec les combinaisons suivantes:

Products: {1, 2, 3}, {1, 3, 2}, {1, 2, 4}, {1, 3, 4}, {1, 4} 
      {2, 1, 3}, {2, 1, 4}, {2, 3, 1}, {2, 3, 4}, {2, 4} 
      {3, 1, 2}, {3, 1, 4}, {3, 2, 1}, {3, 2, 4}, {3, 4} 
      {4} 

Il est presque une permutation, mais il est filtré sur les entrées pour arri plus que ce est requis. Je dois arrêter de prendre d'autres articles, si à tout moment, la somme totale actuelle des valeurs dépasse 15. De cette manière, si j'avais toutes les permutations, j'aurais 24 résultats, mais j'en ai seulement 16.

E.g. si je prends le produit 4 alors je n'ai pas besoin de le combiner avec quoi que ce soit pour faire 15. De même, si je prends le produit 1 alors prends le produit 4, je n'ai plus besoin de ramasser le produit 5 + 15 = 20). J'ai pu faire fonctionner le code en obtenant toutes les permutations (par exemple, here), puis en filtrant ceux qui m'intéressent, mais une fois que vous commencez à obtenir un grand nombre de produits (par exemple 30), vous finissez par avec 4,3 milliards de combinaisons qui provoque des exceptions de mémoire insuffisante.

Comment puis-je créer uniquement les permutations requises en C#?

Answer 1

Ceci est probablement pas la réponse la plus efficace, mais il ne donne la bonne réponse:

void Main() 
{ 
    List<Product> products = new List<Product> { new Product { ProductID = 1, Quantity = 5 }, 
                new Product { ProductID = 2, Quantity = 5 }, 
                new Product { ProductID = 3, Quantity = 8 }, 
                new Product { ProductID = 4, Quantity = 15 }, 
                }; 


    decimal requiredQuantity = 15; 
    if (requiredQuantity < products.Sum(p => p.Quantity)) 
    { 
     var output = Permutations(products, requiredQuantity); 

     output.Dump(); 
    } 
    else 
    { 
     products.Dump(); 
    } 
} 

// Define other methods and classes here 
private List<Queue<Product>> Permutations(List<Product> list, decimal requiredValue, Stack<Product> currentList = null) 
{ 
    if (currentList == null) 
    { 
     currentList = new Stack<Product>(); 
    } 
    List<Queue<Product>> returnList = new List<System.Collections.Generic.Queue<Product>>(); 

    foreach (Product product in list.Except(currentList)) 
    { 
     currentList.Push(product); 
     decimal currentTotal = currentList.Sum(p => p.Quantity); 
     if (currentTotal >= requiredValue) 
     { 
      //Stop Looking. You're Done! Copy the contents out of the stack into a queue to process later. Reverse it so First into the stack is First in the Queue 
      returnList.Add(new Queue<Product>(currentList.Reverse())); 
     } 
     else 
     { 
      //Keep looking, the answer is out there 
      var result = Permutations(list, requiredValue, currentList); 
      returnList.AddRange(result); 
     } 
     currentList.Pop(); 
    } 


    return returnList; 
} 


struct Product 
{ 
    public int ProductID; 
    public int Quantity; 
} 

Answer 2

Voici mon C++ code (peut facilement convertir en code C#)

Pour votre entrée la sortie doit être . Vous avez manqué {4,2,1}, { 4,1,2} ... { 1,2,3,4} ..... comme des combinaisons et des permutations.

const int sz = 50, wmx = 50; 
int qua[sz], fac[sz], dp[sz][sz][wmx], vst[sz][sz][wmx], prs = 0, n, reqQ; 

int rec(int now, int taken, int wTaken) { 

    if (now < 0) { 
     return 0; 
    } 

    if (vst[now][taken][wTaken] == prs) { 
     return dp[now][taken][wTaken]; 
    } 
    vst[now][taken][wTaken] = prs; 

    dp[now][taken][wTaken] = rec(now-1, taken, wTaken) + rec(now-1, taken + 1, wTaken + qua[now]); 
    if ((wTaken + qua[now]) >= reqQ) { 
     dp[now][taken][wTaken] += fac[taken + 1]; 
    } 
    return dp[now][taken][wTaken]; 
} 

int main() { 
    fac[0] = 1; 
    for (int i = 1; i <= sz; i++) { 
     fac[i] = fac[i-1] * i; 
    } 

    while (cin >> n >> reqQ) { 
     for (int i = 0; i < n; i++) { 
      cin >> qua[i]; 
     } 
     prs++; 
     cout << rec(n-1, 0, 0) << endl; 
    } 

    return 0; 
} 

Answer 3

Je vais discuter de la solution en termes de Python parce que je n'ai pas C# installé sur ce Mac, mais C# a itérateurs, donc ce dont je parle va travailler. Tout d'abord, comme vous l'avez découvert, vous ne voulez pas retourner la liste entière. Il consomme une énorme quantité de mémoire. Renvoyez plutôt un itérateur comme dans https://msdn.microsoft.com/en-us/library/65zzykke(v=vs.100).aspx qui retournera chaque élément de votre liste à son tour. En second lieu, vous pouvez construire des itérateurs à partir d'itérateurs. Le premier est celui qui fait des sous-ensembles où le dernier élément vous pousse à votre seuil et au-delà:

def minimal_subset_iter (product, threshold): 
    # Sort smallest to the front so that we skip no combinations that 
    # will lead to our threshold in any order. 
    ids = list(sorted(product.keys(), key=lambda key: (product[key], key))) 

    # Figure out the size of the trailing sums. 
    remaining_sum = [] 
    total_sum = sum(product.values()) 
    for i in range(len(ids)): 
     remaining_sum.append(
      total_sum - sum(product[ids[j]] for j in range(i))) 
    remaining_sum.append(0) 

    # We modify this in place and yield it over and over again. 
    # DO NOT modify it in the return, make a copy of it there. 
    chosen_set = [] 
    def _choose (current_sum, i): 
     if threshold <= current_sum: 
      yield chosen_set 
     elif threshold <= current_sum + remaining_sum[i]: 
      # Can I finish without this element? 
      for x in _choose(current_sum, i+1): 
       yield x 

      # All of the ways to finish with this element. 
      chosen_set.append(ids[i]) 
      current_sum = current_sum + product[ids[i]] 
      for x in _choose(current_sum, i+1): 
       yield x 
      # Cleanup! 
      chosen_set.pop() 

    return _choose(0, 0) 


for x in minimal_subset_iter({1: 5, 2: 5, 3: 8, 4: 15}, 15): 
    print(x) 

Et maintenant, vous avez besoin d'un itérateur qui transforme un sous-ensemble minimal dans toutes les permutations de ce sous-ensemble, où le dernier élément pousse vous au seuil.

Je n'écrirai pas celui-là puisque le principe est simple. Et d'ailleurs vous devez le traduire dans une langue différente. Mais l'idée est d'extraire chaque possibilité pour ce dernier élément qui atteint la fin, d'exécuter les permutations du reste, et d'ajouter le dernier élément avant de le donner.

Cet algorithme sera très efficace sur la mémoire (il garde fondamentalement le dictionnaire et la permutation actuelle) et aussi assez efficace sur les performances (il a beaucoup de listes à créer, mais perdra peu de temps à en créer d'autres) besoin). Cependant, il faut un certain temps pour comprendre cette façon de travailler.

Answer 4

ressemble à seulement deux règle:
1. les éléments prélevés sont distincts.
2. La somme de la quantité d'éléments choisis doit être supérieure à l'objectif, pas seulement égale au but.

Mon exemple ajoute une interface pour le tri. Chaque type de combinaison pouvant atteindre l'objectif est répertorié. Mais j'essaie d'énumérer sous une forme unique pour la lecture. Vous pouvez étendre le travail au sein de chaque combinaison.

PS. à des fins de commande, j'ajoute IComparable, pas très important.

class Product: IComparable 
{ 
    public int ID { get; set; } 
    public uint Qty { get; set; } 

    public int CompareTo(object obj) 
    { 
     if (obj is Product) 
      return this.ID.CompareTo(((Product)obj).ID); 
     else 
      return -1; 
    } 

    public override string ToString() 
    { 
     return string.Format("Product: {0}", this.ID); 
    } 
} 

class Combination : List<Product>, IComparable 
{ 
    public int Goal { get; private set; } 

    public bool IsCompleted 
    { 
     get 
     { 
      return this.Sum(product => product.Qty) >= Goal; 
     } 
    } 

    public Combination(int goal) 
    { 
     Goal = goal; 
    } 

    public Combination(int goal, params Product[] firstProducts) 
     : this(goal) 
    { 
     AddRange(firstProducts); 
    } 

    public Combination(Combination inheritFrom) 
     : base(inheritFrom) 
    { 
     Goal = inheritFrom.Goal; 
    } 

    public Combination(Combination inheritFrom, Product firstProduct) 
     : this(inheritFrom) 
    { 
     Add(firstProduct); 
    } 

    public int CompareTo(object obj) 
    { 
     if (obj is Combination) 
     { 
      var destCombination = (Combination)obj; 
      var checkIndex = 0; 
      while (true) 
      { 
       if (destCombination.Count - 1 < checkIndex && this.Count - 1 < checkIndex) 
        return 0; 
       else if (destCombination.Count - 1 < checkIndex) 
        return -1; 
       else if (this.Count - 1 < checkIndex) 
        return 1; 
       else 
       { 
        var result = this[checkIndex].CompareTo(destCombination[checkIndex]); 
        if (result == 0) 
         checkIndex++; 
        else 
         return result; 
       } 
      } 
     } 
     else 
      return this.CompareTo(obj); 
    } 

    public override int GetHashCode() 
    { 
     unchecked 
     { 
      return this.Select((item, idx) => item.ID * (10^idx)).Sum(); 
     } 
    } 

    public override bool Equals(object obj) 
    { 
     if (obj is Combination) 
      return ((Combination)obj).GetHashCode() == this.GetHashCode(); 
     else 
      return base.Equals(obj); 
    } 
} 

la partie de test fournit la liste des produits et le but.

public static void Test() 
    { 
     var goal = 25; 
     var products = new[] 
     { 
      new Product() { ID = 1, Qty = 5 }, 
      new Product() { ID = 2, Qty = 5 }, 
      new Product() { ID = 3, Qty = 8 }, 
      new Product() { ID = 4, Qty = 15 }, 
      new Product() { ID = 5, Qty = 17 }, 
      new Product() { ID = 6, Qty = 1 }, 
      new Product() { ID = 7, Qty = 4 }, 
      new Product() { ID = 8, Qty = 6 }, 
     }; 

     var orderedProducts = products.OrderBy(prod => prod.ID); 

     //one un-completed combination, can bring back muliple combination.. 
     //that include completed or next-staged-uncompleted combinations 
     Func<Combination, IEnumerable<Combination>> job = null; 

     job = (set) => 
     { 
      if (set.IsCompleted) 
       return new[] { set }.ToList(); 
      else 
      { 
       return orderedProducts 
        .Where(product => set.Contains(product) == false && product.ID >= set.Last().ID) 
        .Select(product => new Combination(set, product)) 
        .SelectMany(combination => job(combination)); 
      } 
     }; 

     var allPossibility = orderedProducts 
      .Select(product => new Combination(goal, product)) 
      .SelectMany(combination => job(combination)) 
      .Where(combination => combination.IsCompleted) 
      .Select(combination => new Combination(goal, combination.OrderBy(product => product.ID).ToArray())) 
      .OrderBy(item => item) 
      .ToList(); 

     foreach (var completedCombination in allPossibility) 
     { 
      Console.WriteLine(string.Join<int>(", ", completedCombination.Select(prod => prod.ID).ToArray())); 
     } 
     Console.ReadKey(); 
    }