Combinaciones únicas de la lista

Question

Absoluta mente en blanco en esto. Ha sido uno de esos días. Pero he estado buscando una solución para obtener combinaciones únicas de una lista de artículos de cierta duración. por ejemplo, dada una lista [a, b, c] y una longitud de 2, devolverá [a, b] [a, c] [b, c] pero no [b, a] [c, a] [c , b]

Para esto encontré varias piezas de código, pero ninguna que parece encajar. El siguiente código parecía mejor ajuste y he estado tratando de alterarla para mis necesidades:

// Returns an enumeration of enumerators, one for each permutation 
// of the input. 
public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count) 
{ 
    if (count == 0) 
    { 
     yield return new T[0]; 
    } 
    else 
    { 
     int startingElementIndex = 0; 
     foreach (T startingElement in list) 
     { 
      IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex); 

      foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1)) 
      { 
       yield return Concat<T>(
        new T[] { startingElement }, 
        permutationOfRemainder); 
      } 
      startingElementIndex += 1; 
     } 
    } 
} 

// Enumerates over contents of both lists. 
public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b) 
{ 
    foreach (T item in a) { yield return item; } 
    foreach (T item in b) { yield return item; } 
} 

// Enumerates over all items in the input, skipping over the item 
// with the specified offset. 
public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip) 
{ 
    int index = 0; 
    foreach (T item in input) 
    { 
     if (index != indexToSkip) yield return item; 
     index += 1; 
    } 
} 

Esto hace lo que se supone que debe hacer, pero devuelve todas las permutaciones, independientemente de ellas es única. Intenté entender qué pieza, si corresponde, de este código cambiar para obtener los valores únicos. ¿O es la mejor manera de implementar esta funcionalidad?

Answer 1

La lista de elementos restantes en la implementación contiene todos los elementos excepto el elemento de inicio actual.

conseguir los artículos que se encuentran después del punto de partida en su lugar:

IEnumerable<T> remainingItems = list.Skip(startingElementIndex + 1); 

Answer 2

En lugar de AllExcept, debe usar una subsección que solo le proporciona los artículos después del que está considerando.

Answer 3

Prueba esto:

void Main() 
{ 
    var list = new List<string> { "a", "b", "c", "d", "e" }; 
    var result = GetPermutations(list, 3); 
} 

IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count) 
{ 
    int i = 0; 
    foreach(var item in items) 
    { 
     if(count == 1) 
      yield return new T[] { item }; 
     else 
     { 
      foreach(var result in GetPermutations(items.Skip(i + 1), count - 1)) 
       yield return new T[] { item }.Concat(result); 
     } 

     ++i; 
    } 
} 

Para un recuento de 2 vuelve esto:

a, b 
a, c 
a, d 
a, e 
b, c 
b, d 
b, e 
c, d 
c, e 
d, e 

Para una cuenta de 3 devuelve esto:

a, b, c 
a, b, d 
a, b, e 
a, c, d 
a, c, e 
a, d, e 
b, c, d 
b, c, e 
b, d, e 
c, d, e 

¿Es esto lo que esperas?

Answer 4

En set-speak, lo que está buscando es un subconjunto del conjunto de potencia basado en la longitud n. Si realiza una búsqueda en Google de "C#" + "Power set", debería darle suficiente para comenzar.

http://en.wikipedia.org/wiki/Power_set

Answer 5

y simplemente para la corrección .. si ya tiene todas las permutaciones (:) y porque es sólo una copia y pegar para mí) con los siguientes extensionmethods puede obtener resultados distintos como este:

var result = permutations.Distinct((p1, p2) => !p1.Differs(p2)); 

solo un ejemplo y si su trabajo con la comparación de las listas de muchos de los otros métodos pueden ser útiles también en otras partes

public static class Extensionmethods 
{ 
    /// <summary> 
    /// Checks if both IEnumerables contain the same values regardless of their sequence 
    /// </summary> 
    /// <typeparam name="T">Type of Elements</typeparam> 
    /// <param name="result">IEnumerable to compare to</param> 
    /// <param name="compare">IEnumerable to compare to</param> 
    /// <returns>Returns false if both IEnumerables contain the same values</returns> 
    public static bool Differs<T>(this IEnumerable<T> result, IEnumerable<T> compare) 
    { 
     if (result == null && compare == null) 
      return false; 
     if (result != null && compare == null) 
      return true; 
     if (result == null && compare != null) 
      return true; 
     return result.Count() != compare.Count() 
      || compare.Where(c => c == null).Count() != result.Where(r => r == null).Count() 
      || compare.Where(c => c != null).Distinct().Any(item => result.Where(r => item.Equals(r)).Count() != compare.Where(r => item.Equals(r)).Count()); 
    } 
    /// <summary> 
    /// Checks if both IEnumerables contain the same values (corresponding to <paramref name="comparer"/> regardless of their sequence 
    /// </summary> 
    /// <typeparam name="T">Type of Elements</typeparam> 
    /// <param name="result">IEnumerable to compare to</param> 
    /// <param name="compare">IEnumerable to compare to</param> 
    /// <param name="comparer">IEqualityComparer to use</param> 
    /// <returns>Returns false if both IEnumerables contain the same values</returns> 
    public static bool Differs<T>(this IEnumerable<T> result, IEnumerable<T> compare, IEqualityComparer<T> comparer) 
    { 
     if (result == null && compare == null) 
      return false; 
     if (result != null && compare == null) 
      return true; 
     if (result == null && compare != null) 
      return true; 
     return result.Count() != compare.Count() 
      || compare.Where(c => c == null).Count() != result.Where(r => r == null).Count() 
      || compare.Where(c => c != null).Distinct().Any(item => result.Where(r => comparer.Equals(item, r)).Count() != compare.Where(r => comparer.Equals(item, r)).Count()); 
    } 

    public static IEnumerable<T> Distinct<T>(this IEnumerable<T> source, Func<T, T, bool> compareFunction, Func<T, int> hashFunction = null) 
    { 
     var ecomparer = new DynamicEqualityComparer<T>(compareFunction, hashFunction); 
     return source.Distinct(ecomparer); 
    } 


} 

internal class DynamicEqualityComparer<T> : IEqualityComparer<T> 
{ 

    public DynamicEqualityComparer(Func<T, T, bool> equalFunction, Func<T, int> hashFunction = null) 
    { 
     this.equalFunc = equalFunction; 
     this.hashFunc = hashFunction; 
    } 

    private Func<T, T, bool> equalFunc; 
    public bool Equals(T x, T y) 
    { 
     if (x == null && y == null) return true; 
     if (x == null) return false; 
     if (y == null) return false; 
     if (hashFunc != null) 
     { 
      if (hashFunc.Invoke(x) != hashFunc.Invoke(y)) return false; 
     } 
     return this.equalFunc.Invoke(x, y); 
    } 

    private Func<T, int> hashFunc; 
    public int GetHashCode(T obj) 
    { 
     if (hashFunc != null) return hashFunc.Invoke(obj); 
     return 0; 
    } 
}