Reminder Kombination aus Kombinationsset

  • C#
  • .NET (FX) 4.0

Es gibt 8 Antworten in diesem Thema. Der letzte Beitrag () ist von 3daycliff.

    Reminder Kombination aus Kombinationsset

    Hey,

    Gegeben sei ein Integer
    $r$
    sowie ein Limit
    $L$
    .
    Finde zwei Integer
    $a, b$
    so dass gilt
    $a \mod b = r$
    . Dabei gilt
    $0 <= a, b <= L$
    .
    Das habe ich auch soweit hingekriegt:

    C#-Quellcode

    1. private static IEnumerable<(uint, uint)> GenerateRemPairs(uint r, uint limit)
    2. {
    3. // Ensure value is not uint maxvalue
    4. if (r == uint.MaxValue)
    5. throw new ArgumentOutOfRangeException(nameof(r));
    6. // Ensure r is smaller then the limit
    7. if(r >= limit)
    8. throw new ArgumentOutOfRangeException(nameof(r));
    9. // Find all possible values for a,b such that a % b = r
    10. for (uint b = r + 1; b <= limit; b++)
    11. for (uint i = 0; i < r; i++)
    12. {
    13. uint a = r + i * b;
    14. if (a <= limit)
    15. yield return (a, b);
    16. }
    17. }


    Ein Beispiel: Wählen wir
    $r=7$
    und
    $L=16$
    .
    Dabei erhalte ich folgende, gültige Kombinationen:

    Quellcode

    1. 7 % 8 = 7
    2. 15 % 8 = 7
    3. 7 % 9 = 7
    4. 16 % 9 = 7
    5. 7 % 10 = 7
    6. 7 % 11 = 7
    7. 7 % 12 = 7
    8. 7 % 13 = 7
    9. 7 % 14 = 7
    10. 7 % 15 = 7
    11. 7 % 16 = 7


    Ich habe allerdings vor, aus all diesen Kombinationen nur eine zufällige zu berechnen, da es enorm viele Kombinationen gibt, wenn der Unterschied zwischen
    $r$
    und
    $L$
    groß ist. Mit anderen Worten, nein, alle Kombinationen berechnen und eine zufällig zu wählen ist nicht die Lösung.
    Ich möchte ein Paar berechnen das folgende Eigenschaften hat:
    $a,b \neq r$
    , außer es gibt kein solches Paar, dann gilt diese Einschränkung nicht.

    Zur Verdeutlichung, mögliche Lösungen aus dem vorrigen Beispiel wären also:

    Quellcode

    1. 15 % 8 = 7
    2. 16 % 9 = 7


    Wie finde ich ein solches Paar ohne alle Möglichkeiten vorzuberechnen und dann jedes einzelne Paar auf oben genannte Bedingung zu prüfen? (Das wäre nämlich sehr ineffizient)
    C# Developer
    Learning C++
    @Rikudo Auf jeden Fall nicht mit yield.
    Mach Dir für die Laufvariablen l und b zufällige Startwerte im erlaubten Bereich und finde den nächsten.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    \begin{align*} a \equiv b \mod r,\quad 0 \leq a,b \leq L \quad\Rightarrow\quad & b \in \{r+1, ..., L\}\text{ und } \\ & a = bx + r \text{ mit } x \in \{0, ..., \frac{(L-r)}{b}\} \\ b > L-r \quad\Rightarrow\quad & x = 0 \quad\Rightarrow\quad a = r \end{align*} Für $x > 0% und damit a \neq r$ wähle $b \in \{r + 1, ..., L - r\}$, sofern $r+1 <= L-r$


    Zusammen (ungetestet):

    C#-Quellcode

    1. uint a, b;
    2. if(r+1 <= L-r) {
    3. b = rand.Next(r+1, L-r+1);
    4. uint x = rand.Next(1, (L-r)/b + 1);
    5. a = b*x + r;
    6. }
    7. else {
    8. b = rand.Next(r+1, L+1);
    9. a = r;
    10. }
    11. return (a, b);

    RodFromGermany schrieb:

    @Rikudo Auf jeden Fall nicht mit yield.
    Mach Dir für die Laufvariablen l und b zufällige Startwerte im erlaubten Bereich und finde den nächsten.

    1)
    $L$
    ändert sich nicht, das wird später immer int.MaxValue sein.
    2) Einen zufälligen Wert für
    $b$
    habe ich ja bereits. Die Frage ist wie ich einen
    $a$
    -Wert finde, der zufällig ist, ohne trial and error.

    Folgendes Beispiel:

    C#-Quellcode

    1. private static (uint, uint) FindRandomRemPair(uint r, uint limit)
    2. {
    3. // Ensure value is not uint maxvalue
    4. if (r == uint.MaxValue)
    5. throw new ArgumentOutOfRangeException(nameof(r));
    6. // Ensure r is smaller then the limit
    7. if(r >= limit)
    8. throw new ArgumentOutOfRangeException(nameof(r));
    9. // Find all possible values for a,b such that a % b = r
    10. for (uint b = r + 1; b <= limit; b++)
    11. {
    12. for (uint i = 0; i < r; i++)
    13. {
    14. uint a = r + i * b;
    15. if (a <= limit && a != r)
    16. return (a, b);
    17. }
    18. if(b == limit)
    19. return (r, b);
    20. }
    21. throw new Exception();
    22. }

    Diese Funktion findet zwar ein gültiges Paar, aber da gibt es ein Problem.
    Es wird immer der erste
    $a$
    -Wert der die Bedingung erfüllt genommen. Da ich nicht weiß wieviele gültige
    $a$
    -Werte noch folgen ist es mir nicht möglich eine zufällige Anzahl an
    $a$
    -Werten zu überspringen bevor ich einen auswähle.
    C# Developer
    Learning C++

    Rikudo schrieb:

    eine zufällige Anzahl an a" role="presentation">a-Werten zu überspringen
    ist eine neue Aufgabenstellung. :/
    Wieso willst Du denn nun Werte überspringen?
    Da Du nicht weißt, ob der erste zufällig gefundene Wert bereits einer der letzten ist, ist das so nicht lösbar.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Nicht das ist keine neue Aufgabenstellung. Ich habe zuvor erwähnt das ich iterieren durch trial and error eigentlich vermeiden möchte.
    Ich würde lieber einen zufälligen
    $a$
    -Wert "errechnen".

    @3daycliff
    Ein sehr interessanter Ansatz. Das ist dem was ich möchte doch schon sehr nahe.
    Ich versuche gerade alles nachzuvollziehen. Ich weiß du hast das nur aus dem Kopf geschrieben, nichtdestotrotz habe ich folgendes festgestellt:
    Bei
    $r=0$
    und bei
    $r > 1073741823$
    (Das entspricht int.MaxValue/2) wird im else-case

    C#-Quellcode

    1. b = random.Next(r + 1, L + 1);

    folgender Fehler geworfen:

    Quellcode

    1. 'minValue' cannot be greater than maxValue


    Es wird versucht einen
    $a$
    -Wert zu finden welcher int.MaxValue überschreitet.

    Vollzitat entfernt. ~Thunderbolt
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Thunderbolt“ ()

    @3daycliff
    $L$
    ist int.MaxValue. Hast du eine Idee wie ich das overflow Problem lösen kann ohne long zu verwenden?
    Hintergedanke ist das ganze später auch für long Werte zu skalieren, und da hätte man dann das selbe Problem.

    C#-Quellcode

    1. private static (int, int) RemCheck(int r, int L)
    2. {
    3. int a, b;
    4. if (r + 1 <= L - r)
    5. {
    6. b = random.Next(r + 1, L - r + 1);
    7. int x = random.Next(1, (L - r) / b + 1);
    8. a = b * x + r;
    9. }
    10. else
    11. {
    12. b = random.Next(r + 1, L + 1);
    13. a = r;
    14. }
    15. return (a, b);
    16. }

    C# Developer
    Learning C++
    Naja, die Next(minValue, maxValue)-Methode aus System.Random liefert einen Wert echt kleiner maxValue und nimmt nur einen Int32 entgegen (long hilft also auch nicht direkt).
    Mit der Anforderung a <= L muss man dann bei dem Ansatz schon +1 rechnen.

    Das einfachste wäre wohl L < int.MaxValue voraussetzen.

    Ansonsten könnte man das ganze leicht umschreiben, indem man das +1 aus dem Methodenaufruf heraus zieht:

    C#-Quellcode

    1. int a, b;
    2. if(r <= L-r-1) {
    3. b = rand.Next(r, L-r) + 1;
    4. int x = rand.Next(0, (L-r)/b) + 1;
    5. a = b*x + r;
    6. }
    7. else {
    8. b = rand.Next(r, L) + 1;
    9. a = r;
    10. }
    11. return (a, b);


    Alternativ auf einen anderen Weg die Zufallszahlen bestimmen.