Παραγωγή τυχαίων αριθμών

jimisvog · 9 Μαρτίου 2016

Καλησπέρα,

Σε ένα project που ασχολούμαι θέλω να προσθέσω μια τυχαιότητα. Χρείαζομαι κάθε μια απο τις Χ οντότητες να περιέχει ν υπο-οντότητες, όμως όλες οι υπο-οντότητες στο σύνολο να είναι Ν.

Έστω οτι Ν = 10 και Χ = 4:

Θέλω π.χ:

x1 = 2,
x2 = 3,
x3 = 1,
x4 = 4

Όπου ισχύει: x1 + x2 + x3 + x4 = N

Έχει κανείς μια ιδέα για το πως μπορώ να το στήσω αλγοριθμικά; Ουσιαστικά θέλω να χωρίσω τα Ν στοιχεία σε Χ κομμάτια.

Kercyn · 9 Μαρτίου 2016

Θες κάθε υπο-οντότητα να είναι ξεχωριστός αριθμός; Αν ναι, τότε μπορείς να έχεις ένα knapsack χωρητικότητας Ν και ένα σετ με διακριτές τιμές από 1 έως Ν-1. Αν το αποτέλεσμά σου έχει λιγότερες τιμές απ' όσες θες, παίρνεις το μεγαλύτερο και προσπαθείς να τον γράψεις ως άθροισμα 2 άλλων αριθμών από το σετ σου κοκ.

Μου φαίνεται πολύ μπακαλίστικη λύση η οποία για μεγάλα Ν θα έχει προβλήματα χρόνου (και όχι μόνο) αλλά ίσως σου δώσει κάποια καλύτερη ιδέα.

jimisvog · 9 Μαρτίου 2016

Όχι δεν έχω κανέναν άλλον περιορισμό εκτός του ο,τι το συνολικό άθροισμα πρέπει να είναι Ν. Για να σου δώσω να καταλάβει τι θέλω να κάνω:

Έχω Χ servers και θέλω κάθε ένας απο αυτούς να έχει έναν random αριθμό απο Virtual Machines, πού όλα τα VM να είναι συνολικά N.

imitheos · 9 Μαρτίου 2016

Αν δεν θέλεις ομοιόμορφη κατανομή και δεν σε ενδιαφέρει να είναι και πολύ δόκιμος ο αλγόριθμος, μπορείς να τρέχεις ένα βρόχο με rand.

	int n = N - (X - 1);

	for (i = 0 ; i < X - 1; i++) {
		x[i] = rand() % n + 1;
		n -= x[i] - 1;
	}
	x[i] = n;

Βρίσκεις κάθε φορά ένα τυχαίο αριθμό στο range που θέλεις και μετά μειώνεις το range κατά τον αριθμό που βρήκες. Αυτό το κάνεις για Χ - 1 στάδια και ο τελευταίος αριθμός θα είναι όσο έμεινε ώστε να δίνει άθροισμα Ν.

Στην αρχή μειώνω το Ν κατά Χ - 1 επειδή πρέπει να μείνουν αποτελέσματα και για τους επόμενους αριθμούς (πχ με Χ = 4 και Ν = 10, θέλεις ο πρώτος αριθμός να είναι το πολύ 7 γιατί αλλιώς δεν θα μείνουν τιμές για τα x2, x3, x4).

x1 = 3, x2 = 5, x3 = 1, x4 = 1, total = 10
x1 = 3, x2 = 2, x3 = 3, x4 = 2, total = 10
x1 = 6, x2 = 2, x3 = 1, x4 = 1, total = 10
x1 = 7, x2 = 1, x3 = 1, x4 = 1, total = 10
x1 = 1, x2 = 1, x3 = 2, x4 = 6, total = 10
x1 = 5, x2 = 3, x3 = 1, x4 = 1, total = 10
κτλ

groot · 9 Μαρτίου 2016

http://stackoverflow.com/questions/11380491/how-to-create-a-list-of-random-integer-vector-whose-sum-is-x

M2000 · 9 Μαρτίου 2016

Μια πρόταση (σε απλό Μ2000 κώδικα)

Το κακό είναι ότι θα μοιράσει τα στοιχεία βάσει της συχνότητας που έρχονται οι τυχαίοι!

Η δεύτερη πρόταση έχει γραμμική απόκριση βάσει μόνο του Χ.

ΓΚ

Let n=10 , x=4, counter=0, total=0
Print Format$("For number {0} we want {1} random numbers with this sum {0}", n, x)
If n>=x Then {
      Let z=x-1
      Dim a(x)=1
      n-=4
      While n>0 {
            a(Random(0, z))++
            n--
            counter++
      }
      
      For i=0 To z {
            total+=a(i)
            Print a(i)
      }
      Print "Sum of parts "; total
      Print "No of loop times "; counter
}

Let n=10 , x=4, counter=0, total=0
Print Format$("For number {0} we want {1} random numbers with this sum {0}", n, x)
If n>=x Then {
      Let z=x-1, p=0
      Dim a(x)=1
      n-=4
      x--
      While x>=0 {
            p=Random(n-x,0)
            a(x)+=p
            n-=p
            x--
            counter++
      }
      a(0)+=n
      For i=0 To z {
            total+=a(i)
            Print a(i)
      }
      Print "Sum of parts "; total
      Print "No of loop times "; counter
}

Νομίζω ότι ο Imitheos έχει παρόμοιο κώδικα..με τόσα βήματα όσο το Χ

Τώρα που διάβασα ότι οι αριθμοί αντιστοιχούν σε servers προφανώς δεν θα πρέπει να είναι ίδιοι! Άρα δεν φτάνει μόνο αυτό!

albNik · 9 Μαρτίου 2016

Παρε Χ random αριθμούς και κανονικοποιησε τους ως προς στο αθροισμα.

Π.χ [4, 12, 6, 8] άθροισμα 30

[4/30, 12/30, 6/30, 8/30]

[13%, 40%, 20%, 27%]

Αν το Ν ειναι π.χ. 200 τα χωρίζεις με ποσοστά δλδ [26, 80, 40, 54]

k33theod · 9 Μαρτίου 2016

Τελικά η τυχαιότητα δεν πιστεύω ότι είναι και πολύ τυχαία. Αν δηλαδή θες το άθροισμα να είναι 10 το χ1 πχ δεν μπορεί να είναι 11 εκτός και αν παίζουν αρνητικοί. Αν χ1=1 χ2=2 καιχ3=3 τότε το χ4 πρέπει να είναι εντελώς τυχαία 6. Εάν το χ1=6 μπορεί το χ2 να είναι τυχαία 7? Δεν νομίζω.

Πιστεύω ότι το πρόβλημα σου είναι να βρεις τα διαφορετικά υποσύνολα φυσικών αριθμών που σου δίνουν το άθροισμα που θέλεις που δεν είναι καθόλου τυχαία αλλά πολύ συγκεκριμένα. Μετά ναι μπορείς να διαλέξεις τυχαία ένα από αυτά τα υποσύνολα

defacer · 9 Μαρτίου 2016

Thinking aloud.

Έστω ότι έχουμε Χ = 4 και Ν = 10. Αν υποθέσουμε ότι τα x1...xN είναι τουλάχιστον 1 έκαστο, ένας προφανώς fair αλγόριθμος (για κάποιο ορισμό του fair ) είναι ο εξής:

x1 = x2 = x3 = x4 = 1
for (i = 0; i < N - X; ++i) {
    κάνε random roll R από 1 ως Χ
    αύξησε κατα 1 την αντίστοιχη xR
}

Το μόνο "πρόβλημα" εδώ είναι ότι αν N >> Χ αυτό μπορεί να αργήσει λίγο γιατί είναι υπολογιστικά γραμμικό στο Ν - Χ ~= Ν. Προφανώς αυτό δεν έχει σημασία για "μικρές" τιμές του Ν (ας πούμε μέχρι 1 εκατομμύριο), but can we do better?

Ας δούμε πιθανοτικά το τι μπορεί να συμβεί μέχρι τέλους. Θα ρίξουμε συνολικά N - X ζαριές. Σε κάθε μία από αυτές υπάρχει 1/Χ πιθανότητα να αυξήσουμε το x1 αντί για κάποιο άλλο νούμερο. Επομένως μετά το σύνολο των ρίψεων συγκεκριμένα για το x1 έχουμε πιθανότητα (1 - 1/Χ)^(Ν-Χ) να μείνει στην αρχική του τιμή 1 (πιθανότητες Λυκείου).

Αυτό τώρα θα το γράψω διαφορετικά. Μετά το πέρας των ρίψεων, για το x1 έχουμε πιθανότητα

P1 = (1/X)^0 * (1 - 1/Χ)^(Ν-Χ) να μείνει 1

P2 = (1/X)^1 * (1 - 1/Χ)^(Ν-Χ-1) να γίνει 2

P3 = (1/X)^2 * (1 - 1/Χ)^(Ν-Χ-2) να γίνει 3

.....

PN-X = (1/X)^(N-X) * (1 - 1/Χ)^0 να γίνει N - X (στην οποία περίπτωση όλα τα άλλα Χn προφανώς θα μείνουν στο 1)

Αυτό διότι δε μας ενδιαφέρει με ποιά ζαριά αυξήθηκε το Xn, ή με άλλα λόγια: είτε το αυξήσω μια φορά με την πρώτη ζαριά είτε με την τελευταία, το αποτέλεσμα είναι το ίδιο για τις ανάγκες του προβλήματος επομένως ισχύουν οι τύποι των πιθανοτήτων όπως τους έχω.

Αν τώρα μπορούσε κανείς να αντιστοιχίσει το αποτέλεσμα μίας μόνο τυχαίας ζαριάς σε κάποιο κατάλληλα επιλεγμένο διάστημα ακεραίων [0, K) σε ένα από τα μέλη του συνόλου { P1, ..., PN-X } με πιθανότητες κανονικοποιημένες ως προς την τιμή του κάθε P τότε θα έβρισκε κατευθείαν (σε Ο(1)) την τελική τιμή του x1.

Επομένως θα μπορούσε να επαναλάβει τη διαδικασία με Χ' = Χ - 1 και Ν' = Ν - x1 για να βρει την τελική τιμή του x'1 (δηλαδή x2 στο αρχικό πρόβλημα) κ.ο.κ. Αυτό θα ήταν υπολογιστικά γραμμικό πάνω στο Χ, πράγμα που βολεύει αν Χ << Ν.

Κάποιος που νιώθει περισσότερα μαθηματικά απο μένα ίσως μπορεί να μας συμπληρώσει τον τρόπο της αντιστοίχισης που λέω στην παραπάνω παράγραφο για να μπορούμε να κάνουμε και υλοποίηση.

jimisvog · 9 Μαρτίου 2016

Αν δεν θέλεις ομοιόμορφη κατανομή και δεν σε ενδιαφέρει να είναι και πολύ δόκιμος ο αλγόριθμος, μπορείς να τρέχεις ένα βρόχο με rand.
	int n = N - (X - 1);

	for (i = 0 ; i < X - 1; i++) {
		x[i] = rand() % n + 1;
		n -= x[i] - 1;
	}
	x[i] = n;
Βρίσκεις κάθε φορά ένα τυχαίο αριθμό στο range που θέλεις και μετά μειώνεις το range κατά τον αριθμό που βρήκες. Αυτό το κάνεις για Χ - 1 στάδια και ο τελευταίος αριθμός θα είναι όσο έμεινε ώστε να δίνει άθροισμα Ν.

Στην αρχή μειώνω το Ν κατά Χ - 1 επειδή πρέπει να μείνουν αποτελέσματα και για τους επόμενους αριθμούς (πχ με Χ = 4 και Ν = 10, θέλεις ο πρώτος αριθμός να είναι το πολύ 7 γιατί αλλιώς δεν θα μείνουν τιμές για τα x2, x3, x4).
x1 = 3, x2 = 5, x3 = 1, x4 = 1, total = 10
x1 = 3, x2 = 2, x3 = 3, x4 = 2, total = 10
x1 = 6, x2 = 2, x3 = 1, x4 = 1, total = 10
x1 = 7, x2 = 1, x3 = 1, x4 = 1, total = 10
x1 = 1, x2 = 1, x3 = 2, x4 = 6, total = 10
x1 = 5, x2 = 3, x3 = 1, x4 = 1, total = 10
κτλ

Παρε Χ random αριθμούς και κανονικοποιησε τους ως προς στο αθροισμα.

Π.χ [4, 12, 6, 8] άθροισμα 30

[4/30, 12/30, 6/30, 8/30]

[13%, 40%, 20%, 27%]

Αν το Ν ειναι π.χ. 200 τα χωρίζεις με ποσοστά δλδ [26, 80, 40, 54]

Thinking aloud.

Έστω ότι έχουμε Χ = 4 και Ν = 10. Αν υποθέσουμε ότι τα x1...xN είναι τουλάχιστον 1 έκαστο, ένας προφανώς fair αλγόριθμος (για κάποιο ορισμό του fair ) είναι ο εξής:
x1 = x2 = x3 = x4 = 1
for (i = 0; i < N - X; ++i) {
    κάνε random roll R από 1 ως Χ
    αύξησε κατα 1 την αντίστοιχη xR
}
Το μόνο "πρόβλημα" εδώ είναι ότι αν N >> Χ αυτό μπορεί να αργήσει λίγο γιατί είναι υπολογιστικά γραμμικό στο Ν - Χ ~= Ν. Προφανώς αυτό δεν έχει σημασία για "μικρές" τιμές του Ν (ας πούμε μέχρι 1 εκατομμύριο), but can we do better?

Ας δούμε πιθανοτικά το τι μπορεί να συμβεί μέχρι τέλους. Θα ρίξουμε συνολικά N - X ζαριές. Σε κάθε μία από αυτές υπάρχει 1/Χ πιθανότητα να αυξήσουμε το x1 αντί για κάποιο άλλο νούμερο. Επομένως μετά το σύνολο των ρίψεων συγκεκριμένα για το x1 έχουμε πιθανότητα (1 - 1/Χ)^(Ν-Χ) να μείνει στην αρχική του τιμή 1 (πιθανότητες Λυκείου).

Αυτό τώρα θα το γράψω διαφορετικά. Μετά το πέρας των ρίψεων, για το x1 έχουμε πιθανότητα

P1 = (1/X)^0 * (1 - 1/Χ)^(Ν-Χ) να μείνει 1

P2 = (1/X)^1 * (1 - 1/Χ)^(Ν-Χ-1) να γίνει 2

P3 = (1/X)^2 * (1 - 1/Χ)^(Ν-Χ-2) να γίνει 3

.....

PN-X = (1/X)^(N-X) * (1 - 1/Χ)^0 να γίνει N - X (στην οποία περίπτωση όλα τα άλλα Χn προφανώς θα μείνουν στο 1)

Αυτό διότι δε μας ενδιαφέρει με ποιά ζαριά αυξήθηκε το Xn, ή με άλλα λόγια: είτε το αυξήσω μια φορά με την πρώτη ζαριά είτε με την τελευταία, το αποτέλεσμα είναι το ίδιο για τις ανάγκες του προβλήματος επομένως ισχύουν οι τύποι των πιθανοτήτων όπως τους έχω.

Αν τώρα μπορούσε κανείς να αντιστοιχίσει το αποτέλεσμα μίας μόνο τυχαίας ζαριάς σε κάποιο κατάλληλα επιλεγμένο διάστημα ακεραίων [0, K) σε ένα από τα μέλη του συνόλου { P1, ..., PN-X } με πιθανότητες κανονικοποιημένες ως προς την τιμή του κάθε P τότε θα έβρισκε κατευθείαν (σε Ο(1)) την τελική τιμή του x1.

Επομένως θα μπορούσε να επαναλάβει τη διαδικασία με Χ' = Χ - 1 και Ν' = Ν - x1 για να βρει την τελική τιμή του x'1 (δηλαδή x2 στο αρχικό πρόβλημα) κ.ο.κ. Αυτό θα ήταν υπολογιστικά γραμμικό πάνω στο Χ, πράγμα που βολεύει αν Χ << Ν.

Κάποιος που νιώθει περισσότερα μαθηματικά απο μένα ίσως μπορεί να μας συμπληρώσει τον τρόπο της αντιστοίχισης που λέω στην παραπάνω παράγραφο για να μπορούμε να κάνουμε και υλοποίηση.

Ακριβώς για κάτι τέτοια "έξυπνα" posts αγαπάω αυτό το φόρουμ. Με βοηθήσατε και με το παραπάνω με μπόλικους τρόπους.

Ευχαριστώ guys

ALLisCHAOS · 10 Μαρτίου 2016

Έκατσα διάβασα μόνο την ερώτηση, είδα ότι δόθηκαν πολλές απαντήσεις και χωρίς να δω κάποια πήγα βρήκα μια δικιά μου και μετά ξανα μπήκα να δω (από περιέργεια?)με ποιον θα ταίριαζε (αν ταίριαζε ) η λύση μου.
+1 Λοιπόν στο @imitheo η πρώτη λύση που μου ήρθε στο μυαλό ήταν και σε μένα αυτή

edit: έξυπνη προσέγγηση από defacer

imitheos · 10 Μαρτίου 2016

Ακριβώς για κάτι τέτοια "έξυπνα" posts αγαπάω αυτό το φόρουμ. Με βοηθήσατε και με το παραπάνω με μπόλικους τρόπους.

Ευχαριστώ guys

Ο δικός μου τρόπος δεν ήταν έξυπνος αλλά η πιο απλή λύση που έρχεται στο μυαλό του οποιουδήποτε, όπως επιβεβαίωσε και ο AllisChaos.

Δεν λαμβάνει υπόψιν ούτε το load που μπορεί να έχει ο Κ server, ούτε τις δυνατότητες του επεξεργαστή αν μιλάμε για διαφορετικά μηχανήματα ούτε τίποτα και απλά κόβει ένα range σε κομμάτια. Ακόμη και ο τρόπος που ανήγαγα την έξοδο της rand στο range με τη χρήση του υπολοίπου της διαίρεσης είναι μη-βέλτιστος όπως έχουμε πει σε πολλά άλλα μηνύματα. Το έγραψα έτσι πιο πολύ για να πάρεις ιδέες και να οδηγηθείς σε κάτι καλύτερο ή μέχρι να ποστάρει κάποιος άλλος κάτι καλύτερο.

defacer · 10 Μαρτίου 2016

^ Το μεγαλύτερο θέμα που βλέπω με τη λύση σου είναι πως είναι biased να βάζει μικρά νούμερα στα τελευταία x.

groot · 10 Μαρτίου 2016

Να γράψω και εγώ μία προσέγγιση... μπορεί να βελτιστοποιηθεί με χρήση generators και με καλύτερο update/διαχείριση της μέγιστης τιμής για κάθε κατανομή εργασιών... αλλά δεν θα το κάνω τώρα

επίσης, η list για τα initial_states είναι λάθος (από θέμα μνήμης) αλλά το έκανα για να φανεί η λογική.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools
import math
import random

nb_servers = 4
nb_vms = 10
accept_empty = False


def make_all_possible_combinations():
   max_vm = int(math.floor(nb_vms/nb_servers))
   # r = range(max_vm+1)
   # initial_states = list(itertools.product(r = range(max_vm+1), repeat=nb_servers))
   final_states = []
   for initial_state in itertools.product(range(max_vm+1), repeat=nb_servers):
       if not accept_empty and not all(initial_state):
           continue
       max_to_add = nb_vms - max_vm
       while sum(initial_state) < nb_vms:
           rand_index = random.randint(0, nb_servers)
           rand_val = random.randint(0, max_to_add)
           if sum(initial_state) + rand_val > nb_vms:
               continue
           initial_state[rand_index] += rand_val
       final_states.append(initial_state)
   return final_states


def main():
   all_combinations = make_all_possible_combinations()
   print all_combinations[random.randint(0, len(all_combinations))]


if __name__ == '__main__':
   main()

# EOF

Σύνδεση

Παραγωγή τυχαίων αριθμών

Προτεινόμενες αναρτήσεις

jimisvog

Kercyn

jimisvog

imitheos

groot

M2000

albNik

k33theod

defacer

jimisvog

ALLisCHAOS

imitheos

defacer

groot

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

Σύνδεση