serie zbiorów słów z powtórkami

0

Mamy dane powiedzmy że N = 100 zbiorów, i każdy składa się z m = 50 różnych haseł.
Hasłami są tu słowa ze słownika, który zawiera n = 10-20 tysięcy pozycji.

Te zbiory po 50 haseł są losowe, znaczy wybieramy losowo 50 sztuk ze słownika;
i tak robimy 50 czy nawet 100 zbiorów po 50 haseł.

Hasła w każdym zbiorze są różne, ale te z jednego zbioru mogą się już powtarzać w innych zbiorach.
Szanse powtórzenia w dowolnych dwóch zbiorach są niewielkie, chyba grubo poniżej 1 słowa... może nawet 0.1, czyli jedno na 10 par;

jednak przy 100 zbiorach powtórzeń będzie już sporo - z 10% chyba, czyli aż 5 haseł / zbiór.

Zadanie do rozwiązania - algorytm który:
tworzy serię zestawów, w której te powtarzane hasła będą jak najbardziej odległe od siebie.

Przykładowo gdy mamy słowo RAMA, które powtarza się w dwóch zestawach,
wówczas w utworzonej serii te dwa zestawy mają być maksymalnie oddalone od siebie,
tz. gdy pierwszy zestaw ustawimy na początku serii, wówczas ten drugi ma być gdzieś daleko - najlepiej na końcu.

0
  1. Losujesz 5000 haseł ze słownika (skoro ma 10-20 tyś pozycji to żaden problem).
  2. Dzielisz te 5000 haseł na 100 zbiorów (masz gwarancje że się nie powtórzą).
0
_13th_Dragon napisał(a):

Losujesz 5000 haseł ze słownika (skoro ma 10-20 tyś pozycji to żaden problem).

Dzielisz te 5000 haseł na 100 zbiorów (masz gwarancje że się nie powtórzą).

Niestety, ale tak nie da rady.
Te słowa w każdym zbiorze nie są dowolne, lecz są dobierane wg innych reguł... które są tu nieistotnie.

Zbiory tworzymy niezależnie od siebie w oparciu o słownik.
Potem mamy gotowe 100 zbiorów po 50 haseł, i dopiero teraz to 'sortujemy' w taki sposób, aby powtórki haseł były niezauważalne, czyli maksymalnie odległe.

0

Chodzi tu także o to że algorytm maksymalizacji odstępów pomiędzy powtarzanymi słowami,
pozwoli na tworzenie dowolnie długich serii, w których ten odstępy będzie zachowany,
co znaczy że mogę utworzyć nawet i 1000 zbiorów po 50 haseł, w której dowolne hasło powtarza się np. minimum co 60 zbiorów!

A to oznacza, że gdy wybierzemy dowolny podciąg o długości 60 z takiej serii, nawet i dowolnie długiej - neverending!
wówczas nie będzie w nim ani jednego powtórzonego hasła, czyli będzie tam: 60 * 50 = 3000 różnych haseł!

0

W takim razie:

  1. Tworzysz drzewo gdzie węzłami są te twoi zbiory
  2. Wyliczasz krawędzi takiego drzewa jako ilość powtarzających się słów w łączonych węzłach
  3. Znajdujesz najkrótszą drogę w drzewie (np Dijkstra - odpalany N razy gdzie N - ilość węzłów)
0

Nie wiem czy to jest chociaż kompatybilne z moim układaniem serii, a jeśli nawet to byłoby to chyba wyliczanie wszystkich permutacji zbiorów, czyli 100! = 10150. Z milion lat by to trwało. :)

0

Nie wiem jak to chcesz robić, bo Dijkstra oblicza sumę wag, a tu mamy zupełnie coś innego:
maksimum odległości pomiędzy powtórkami, co nie ma przecież żadnego związku z ilością powtórzeń,
którą sugerujesz minimalizować.

Liczba powtórek jest tu jednakowa - stała dla dowolnej serii.

0
_13th_Dragon napisał(a):

Wyliczasz krawędzi takiego drzewa jako ilość powtarzających się słów w łączonych węzłach

Dla dwóch list:
A, 3, B, 4, C, D
F, G, 3, 4
Koszt będzie wynosić 2 więc przejdzie tą krawędzią tylko jeżeli nie ma innego wyjścia.

0
_13th_Dragon napisał(a):
_13th_Dragon napisał(a):

Wyliczasz krawędzi takiego drzewa jako ilość powtarzających się słów w łączonych węzłach

Dla dwóch list:
A, 3, B, 4, C, D
F, G, 3, 4
Koszt będzie wynosić 2 więc przejdzie tą krawędzią tylko jeżeli nie ma innego wyjścia.

Nawet nie wiem co reprezentują te listy...

Twoja metoda nie daje maksymalizacji odległości pomiędzy powtórkami w serii,
a tylko minimalizuje powtórki pomiędzy sąsiadami w serii.

I przykładowo dla zbiorów, które nazwijmy sobie: A, B, C, D, ...
mamy powtórki - te wagi krawędzi: A-B = 1, i jeszcze P-Q = 1, a pozostałe pary są zerami.

Algorytm obliczy minimum = zero, oczywiści, i np. takie:
A - C - B - D - ... P - S - T- Q, suma wag = 0

A i B są tu odległe o 2, zaledwie... a mogę zrobić tak:
A - P............ B - Q, i tu jest maksymalna odległość pomiędzy powtórkami.

dystans A-B = P-Q = n-1 >> 2

0

Co za ludzi, zero myślenia, wszystko trzeba rozrzuć i do buzi włożyć.
Szukasz swego ułożenia wśród ścieżek o minimalnej długości znalezionych poprzez Dijkstra, tych ścieżek już nie będzie dużo.

0
_13th_Dragon napisał(a):

Co za ludzi, zero myślenia, wszystko trzeba rozrzuć i do buzi włożyć.
Szukasz swego ułożenia wśród ścieżek o minimalnej długości znalezionych poprzez Dijkstra, tych ścieżek już nie będzie dużo.

Co za barany, z zerem mózgu - żeby nie odróżniać min od sum.

10100 - tyle będzie zerowych, czyli z drogą = 0, i max >= 2.

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