Program do tworzenie kombinacji liczb ze zbiorów na podstawie kryteriów

0

Cześć !
Nie wiedziałem jak to dokładnie w tytule wątku ująć więc najlepiej od razu zobaczcie do załącznika :)
Jest tam plik excela w którym dokładnie opisałem wszystko.
W treści postu też to opiszę ale w excelu to lepiej wygląda :)

W skrócie to szukam sposobu na pokazanie wszystkich możliwych kombinacji liczb pobieranych z danych zbiorów.
W załączniku mam 3 zbiory i 15 liczb powtarzających się - docelowo chciałbym wybieram sobie liczbę zbiorów i w nich ustawiam liczby i ustalać kryteria.

1 zbiór ma liczby: 1,2,3,4,5 = 1 zbiór pokazuje liczby które nie mogą występować razem w jednym zestawie.

2 zbiór ma liczby: 4,5,6,7,8,9,10 = 2 zbiór pokazuje że maksymalnie 2 liczby z tego zbioru mogą być w jednym zestawie.

3 zbiór ma liczby: 8,9,10,11,12,13,14,15 = 3 zbiór pokazuje ze max 3 liczby można z niego wybrać do jednego zestawu.

Czyli przykładowe zestawy mogą być takie 6,7 i 11,12,13, + 1 lub 6,7 i 11,12,13, +2 lub 6,7 i 11,12,13, + 3 ale nie może być wylosowany zestaw 6,7 i 11,12,13, + 4 i 6,7 i 11,12,13, +5 - dodatkowo np 4 i 5 są w 2 zbiorze z którego można wziąć 2 liczby ale są także w 1 zbiorze z którego można wybrać max 1 liczbę - czyli na podstawie zbadania tych 2 zbiorów wniosek jest taki że liczby 4 i 5 nie mogą być w 1 zestawie :)

W tym przykładzie kombinacji będzie pewnie bardzo dużo ale docelowo będę chciał mieć takich zbiorów np 20 i w nim powtarzające się liczby i z każdego będzie można wybrać od 1 do np 3 liczb więc wtedy liczba kombinacji się znacznie zmniejszy bo w 1 zbiorze np 1 nie może się łączyć z 5 a w innym z 6 a w jeszcze innym z 7 itp
Chodzi o to że gdy teraz ręcznie muszę każdą liczbę sprawdzać tak w przyszłości chciałbym aby program sam to robił :)

Aha i liczby się w zbiorach powtarzają ale w wylosowanych zestawach nie mają się powtarzać.
Mam nadzieję że zostałem zrozumiany - jeśli plik załącznika ma być inny to proszę napisać.

0

Czy chodzi ci o coś takiego:

Masz zbór A liczb, z których trzeba generować wszystkie kombinacje x-elementowe bez powtórzeń.
Równocześnie kombinacje mają ograniczenia, takie że:

  1. w każdej kombinacji nie więcej niż jeden element należy do danego zbioru B1
  2. w każdej kombinacji nie więcej niż dwa elementy należą do danego zbioru B2
  3. w każdej kombinacji nie więcej niż trzy elementy należą do danego zbioru B3
    Oczywiście zbiory B1, B2, B3 muszą być rozłączne.
0

już mi mówiono że piszę niezrozumiale - ale tak to przeważnie jest jak rozmawia laik z ekspertem :)

  1. elementy z danego zbioru B1 (podzbiór A) nie mogą występować razem w tej samej kombinacji (czyli maksymalnie jeden element z tego podzbioru może być w zbiorze A.
  2. maksymalnie DWA elementy z danego zbioru B2 (podzbiór A) mogą występować w jednej kombinacji,
  3. maksymalnie trzy elementy z danego zbioru B3 (podzbiór A) mogą wystąpić w jednej kombinacji.

Czyli na podstawie nr1 kombinacja liczb nie może zawierać jednocześnie liczb 1 i 2, 1 i 3, 1 i 4, 1 i 5, 2 i 3, 2 i 4, 2 i 5 itd
Ale rozchodzi się o to że liczby się powtarzają - czyli na podstawie zbioru B2 4 i 5 mogą być w jednej kombinacji ale na podstawie zbioru B1 nie mogą więc wniosek ogólny jest taki że razem być nie mogą w zbiorze A.

1

dobra poprawiłem swoją treść, tylko żeby wszystko było jasne: potrzebne ci kombinacje bez powtórzeń.

Ja bym zrobił tak:
policz zbóir C stanowiący dopełnienie zbioru A z sumy zbiorów B1, B2, B3.
W ten sposób będziesz miał 4 zbiory rozłączne B1, B2, B3, C pokrywające cały zbiór A.

Następnie:
Pętla po i=0,1 (liczbie elementów branych ze zbioru B1)
pętla po wszystkich zwykłych kombinacjach i-elementowych zbioru B1
Pętla po j=0,1,2
pętla po wszystkich zwykłych kombinacjach j-elementowych zbioru B2
Pętla po k=0,1,2,3
pętla po wszystkich zwykłych kombinacjach k-elementowych zbioru B3
pętla po wszystkich zwykłych kombinacjach n-i-j-k-elementowych zbioru C
połącz wszystkie podkombinacje - to jest twój wynik

generator zwykłych kombinacji znajdziesz w internecie.

0

tak bez powtórzeń - zabieram się za szukanie

1

A moja propozycja to wykorzystanie zbiorów i uniezależnienie samego algorytmu od ilości i rodzaju zbiorów B

dane są:

  • zbiór A
  • lista pewnych podzbiorów zbioru A: [B0, ..., Bn]
  • lista liczba: [b0, ..., bn], gdzie liczba bi określa ile maksymalnie elementów ze zbioru Bi może znajdować się w pewnym zbiorze, żeby był on akceptowalny
    szukana:
  • lista wszystkich podzbiorów zb. A, akceptowalnych (każda) przez wszystkie podzbiory B

moja propozycja rozwiązania:

  1. generujesz podzbiory zbioru A (nie generuj wszystkich, niech pewną sugestią będzie mój algorytm w Prawdopodobieństwo uszkodzeń do m elementów z N)
  2. dla danego wygenerowanego podzbioru C, sprawdzasz czy ilość elementów z {części wspólnej zbiorów: C i Bi} <= bi, jeśli tak, dodajesz go do listy dobrych wyników i możesz wykorzystać przy dalszym generowaniu (1.)
0

notexists -> chodzi Ci o funkcję z postu 2011-01-21 23:18 ?

1

tak, ale to tylko podpowiedź co do sposobu generowania, trzeba jeszcze dodać odpowiednie warunki w środku, postaraj się zrozumieć zasadę działania:)

1

Nie można przekombinować. Cały problem wynika z tego, że w zbiorze B jest 4 i 5 z A, tak więc zbiory te nie są rozłączne. Wystarczy za B przyjąć B/A ={6,7,8,9,10} i znika problem. Podobnie z C=C/B, czyli C={11,12,13,14,15}. Oczywiście zbiory możesz mieć jakie chcesz, ale program przed generowaniem powinien je skorygować i zrobić rozłącznymi. Teraz tylko generowania wariacji bez powtórzeń.

0

ojej, dla mnie to jest czarna magia ...
wiem że to nieładnie prosić o gotowca ale jeśli ktoś poratuje to postaram się odwdzięczyć :)
chyba źle zrozumiałem pojęcie "kombinacje bez powtórzeń":

  1. chodzi o to że jeśli liczba 1 zostanie raz wylosowana to już później nie jest losowana ?
  2. czy może chodzi o cały zestaw liczb ?
    bo jeśli chodzi o nr1 to powtórzenia oczywiście są wskazane ...
0

No ale co: umiesz programować, czy w ogóle nie masz o tym pojęcia? Jak nie masz zamiaru tego sam napisać, to szkoda czasu na wyjaśnianie. Możesz zlecić to do zrobienia za pieniądze i będziesz miał. Jako ciekawostkę dodam, że dla podanego przez ciebie przykładu wychodzi 500 różnych zbiorów po 6 elementów. To trochę dużo, a zważywszy, że masz więcej niż trzy mieć, to może się okazać za dużo.

0

zbiorów będzie więcej ale liczb będzie 15 może max 20 i będą się powtarzać w różnych zbiorach - np na podstawie podzbioru b1 liczba 1 nie może się łączyć z 2,3,4 ale dodatkowo w podzbiorze np b7 liczba 1 nie może łączyć się z liczbami 8 i 9 i jeśli będę miał te kilka/naście podzbiorów to z każdego maksymalnie 3 liczby będą mogły należeć do głównej kombinacji liczb - więc chodzi o to że tych zależności między danymi liczbami będzie dużo i przez to wydaję mi się że kombinacji nie będzie strasznie dużo ...
także jeśli nie są to duże kwoty za zrobienie takiego programu to proszę do mnie pisać :) może się dogadamy bo niestety nie mam pojęcia o programowaniu i sam sobie nie poradzę ...

1 użytkowników online, w tym zalogowanych: 0, gości: 1