0
votes

Différent sommet du compteur d'un ensemble donné

Je travaille sur ce code (crédits à Shreyanshi Arun pour le code de base) qui imprime les sommes de tous les sous-ensembles d'un ensemble donné: xxx pré>

J'essaie de l'adapter à recevoir Un compte strong> de combien de sommes sont possibles. Comme je l'ai quitté le code, la variable K sert de compteur de somme. Cependant, j'aimerais que ce compteur augmente seul strong> lorsque la somme résultante n'est égale à aucune précédente. P>

Par exemple, dans ce code, le résultat est comme celui-ci:

19.0 14.0 14.0 9.0 16.0 11.0 11.0 6.0 17.0 12.0 12.0 [...]
Combinations: 256

python combinations subset

1 commentaires

Peut-être essayer d'ajouter du résultat à l'ensemble, vous pouvez utiliser la longueur de définie comme nombre de combinaisons

3 Réponses :

2
votes

créer un ensemble pour contenir toutes les sommes. Ajoutez chaque somme à l'ensemble et à la fin de la longueur de l'ensemble sera le nombre de sommes différentes.

def subsetSums(arr, l, r, sum=0, allSums = None):
    if allSums is None:
        allSums = set()
    # Print current subset
    if l > r:
        allSums.add(sum)
        print(sum,end=" ")
        return len(allSums)

    # Subset including arr[l]
    subsetSums(arr, l + 1, r, sum + arr[l], allSums)

    # Subset excluding arr[l]
    return subsetSums(arr, l + 1, r, sum, allSums)

arr = [0.5, 0.5, 1.5, 1.5, 2, 3, 5, 5]
n = len(arr)

k = subsetSums(arr, 0, n - 1)

1 commentaires

Parfait! Merci beaucoup.

1
votes

Une meilleure approche ici pourrait conserver une table de hash pour vérifier les sommes déjà apparues

def subsetSums(arr, l, r,sum=0):
# Print current subset
if l > r:
    global k
    global sumHash
    print(sum, end=" ")
    if(sum not in sumHash):
        k += 1
    sumHash[sum] = True
    return

# Subset including arr[l]
subsetSums(arr, l + 1, r,sum + arr[l])

# Subset excluding arr[l]
subsetSums(arr, l + 1, r, sum)


k = 0
sumHash = dict()
arr = [0.5, 0.5, 1.5, 1.5, 2, 3, 5, 5]
n = len(arr)

subsetSums(arr, 0, n - 1)

print("\n Combinations:", k)

0 commentaires

2
votes

Au lieu de suivre toujours les 2 sous-sols ^{n sup>, je construirais simplement l'ensemble des sommes telles que ceci:}

>>> len(reduce(lambda sums, x: sums | {s + x for s in sums}, arr, {0}))
39

0 commentaires