Finden des N-ten Elements in einer Liste aller möglichen Zahlen

Question

Finden des N-ten Elements in einer Liste aller möglichen Zahlen

Mathematik
Kombinatorik
elementare Mengenlehre
Elementarzahlentheorie

1110101001

Dies ist eine Erweiterung meiner Frage hier :

Bei einer bestimmten Anzahl von Ziffern, von denen jede einen bestimmten Bereich von 1 bis zu einer bestimmten Zahl hat, was wäre das N-te Element in der Liste aller Permutationen von ihnen, die gefunden werden, indem zuerst die innersten Ziffern modifiziert werden.

Beispiel: Bei 3 Ziffern, wobei die erste einen Bereich von [1..3], die zweite [1..2] und die dritte [1..4] hat, wäre die Liste

Wie würden Sie das N-te Element dieser Arten von Mengen finden? Umgekehrt, bei einer gegebenen Zahl, wie würden Sie die Position in dieser Menge finden?

Gerhard

Kennen Sie das kartesische Produkt?

1110101001

Ich sehe, wie es verwendet werden könnte, um das gewünschte Set zu generieren, aber ich sehe nicht, wie es hilft, ein bestimmtes Element davon zu finden.

Asaf Karagila

Sie haben Tags für diskrete Mathematik, reelle Analyse und Fourier-Transformation vergessen.

Antworten (1)

Finden des N-ten Elements in einer Liste aller möglichen Zahlen

Ich sehe, wie es verwendet werden könnte, um das gewünschte Set zu generieren, aber ich sehe nicht, wie es hilft, ein bestimmtes Element davon zu finden.
Sie haben Tags für diskrete Mathematik, reelle Analyse und Fourier-Transformation vergessen.

Ramchandra Apte · Answer 1

Lassen $S$ sei die Liste der Anzahl möglicher Werte für jede Position in der Liste und let $n$ die Position in der Liste sein. Lassen $i$ Anfangs die Länge der Elemente der Liste sein. Der Prozess zum Erhalt des Elements ist: $q = n/(prod_{x=0}^{i}S_i)$

$n = n\bmod prod_{x=0}^{i}S_i+1$

$i = i-1$

Und jeder nachfolgende Wert von $n$ ist der $i$ te Ziffer des Elements.

Bei einem gegebenen Element ist die Position $\sum_{x=0}^{\text{length of the elements of the list}}\prod_{x=0}^{i}\times(\text{xth digit of the element from left to right}-1)$

Grundsätzlich ist dieses Problem ein degenerierter Fall (ein allgemeiner Fall) der Umwandlung in Basen, außer dass 1 für 0, 2 für 1 verwendet wird (also würde 1111 in dieser Liste 0000 zuordnen) usw. Ich werde bald einen Beweis veröffentlichen . Nicht sicher, ob es richtig ist; werde dies später verifizieren. Auch die Ausgabe/Eingabe kann nullindiziert sein (beginnend bei Null).

In der ersten Formel wurde ein Produkt mit dem Index x verwendet, aber ich sehe dieses x nicht im S_i. Sollte das S_x sein? Könnten Sie bitte die Verwendung anhand eines Beispiels demonstrieren?
Würden Sie nicht auch ein Modulo benötigen, um die Schleife zu berücksichtigen?

Finden des N-ten Elements in einer Liste aller möglichen Zahlen

1110101001

Gerhard

1110101001

Asaf Karagila

Antworten (1)

Ramchandra Apte

1110101001

1110101001

Vergleich zweier Sammlungen von 4-Tupeln unter Verwendung der Kombinatorik - kompliziertere Version

Wie viele nahezu perfekte Permutationen gibt es?

Eine Frage zu einem Sonderfall des Inklusions-Exklusions-Prinzips

kombinatorischer Identitätsnachweis mit Multisets

Wenn 5 ganze Zahlen gegeben sind, zeigen Sie, dass Sie zwei finden können, deren Summe oder Differenz durch 6 teilbar ist.

Auswahl eines Elements aus jeder Menge von Mengen, sodass keine zwei Elemente gleich sind.

tWie viele Möglichkeiten gibt es, eine Menge S unter den folgenden Einschränkungen in zwei Teilmengen aufzuteilen?

Wie viele eindeutige Zahlen erhält man, wenn man zwei natürliche Zahlen multipliziert, die kleiner als NNN sind?

Kombinatorik und mengentheoretische Frage

Sei A={1,2,3,4,5,6,7,8,9,0,20,30,40,50}A={1,2,3,4,5,6,7,8 ,9,0,20,30,40,50}A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}. 1. Wie viele Teilmengen der Größe 2 gibt es? 2.Wie viele Teilmengen gibt es insgesamt?