Algorithmus gesucht: Zahl in zufällig große Teile zerlegen (mit Nebenbedingungen)

[Mike M. (Gast)]

Hallo zusammen,

gegeben ist folgende Problemstellung:
1) Eine gegebene Zahl N soll in M Teile (m_1, ..., m_M) zerlegt werden, 
so dass die Summe dieser Teile wieder N ergibt. Sowohl N und M sind 
jeweils vorgegeben.

Für dieses Problem kursieren bereits einige Algorithmen im Internet (s. 
https://stackoverflow.com/questions/1581394/split-value-in-24-randomly-sized-parts-using-c-sharp 
oder 
https://stackoverflow.com/questions/14583566/split-number-in-random-parts)

nun habe ich aber noch folgende weitere Anforderen an die M Teile:
2) jeder Teil darf minimal den Wert 0 annehmen
3) jeder Teil darf maximal einen jeweils für jeden Teil separat 
definierten Wert annehmen (max_1, ..., max_M)

Selbstverständlich wird nun N so gewählt, dass diese Bedingungen auch 
erfüllt werden können.


Folgende triviale Lösung kam mir zuerst in den Sinn:
Für jeden Teil m_i wird nacheinander eine zufällige Zahl gewählt, so 
dass m_i <= max_i, N nicht überschritten wird und mit den restlichen 
Teilen noch N erreicht werden kann.

Diesen Ansatz habe ich einmal beispielhaft in C++ implementiert:

#include <iostream>
#include <random>
#include <stdexcept>
#include <vector>

typedef std::vector<float> vector_t;

std::mt19937 rng;


vector_t get_random_numbers(const vector_t& max_values, float target_sum)
{
  float sum_max_values = 0.0f;

  vector_t min_values;

  for(auto iter = max_values.rbegin(); iter != max_values.rend(); ++iter)
  {
    min_values.insert(min_values.begin(), target_sum - sum_max_values);
    sum_max_values += *iter;
  }

  if(sum_max_values < target_sum)
  {
    throw std::range_error("could not reach target value");
  }

  vector_t result;
  float sum = 0.0f;

  for(size_t i = 0; i < max_values.size(); i++)
  {
    const float min = std::max(0.0f, min_values[i] - sum);
    const float max = std::min(max_values[i], target_sum - sum);

    std::uniform_real_distribution<float> uniform_distribution(min, max);
    const float value = uniform_distribution(rng);
    
    result.push_back(value);
    sum += value;
  }

  return result;
}


int main()
{
  std::random_device rd;
  rng.seed(rd());
    
  const vector_t max_values = {1.0f, 1.0f, 0.5f, 1.0f};
  const float target_sum    = 3.0f;

  auto result = get_random_numbers(max_values, target_sum);

  std::cout << "values:" << std::endl;

  for(auto value : result)
  {
    std::cout << value << std::endl;
  }
  
  std::cout << "sum: " << std::accumulate(result.begin(), result.end(), 0.0f);
}

Allerdings bin ich nun mit der Verteilung der Werte noch nicht ganz 
zufrieden. Dieses müssen zwar nicht zwingend uniform verteilt sein, 
jedoch wäre eine etwas gleichmäßigere Verteilung wünschenswert.

So konvergieren für die Eingabe mit {1.0, 1.0, 1.0, 1.0, 1.0, 1.0} für 
die Maximalwerte und N = 5.0 die Werte bspw. gegen: {0.5, 0.75, 0.875, 
0.9375, 0.96875}. Dies ergibt sich auch schon prinzipbedingt aus obigen 
Ansatz. Notfalls könnte ich die M Teile bei jedem Aufruf zuerst zufällig 
umsortieren. Vielleich hat allerdings jemanden noch einen besseren 
Ansatz.


Vielen Dank schon einmal,
Mike

[asdfasd (Gast)]

> 1) Eine gegebene Zahl N soll in M Teile (m_1, ..., m_M) zerlegt werden,
> so dass die Summe dieser Teile wieder N ergibt. Sowohl N und M sind
> jeweils vorgegeben.
> 2) jeder Teil darf minimal den Wert 0 annehmen
> 3) jeder Teil darf maximal einen jeweils für jeden Teil separat
> definierten Wert annehmen (max_1, ..., max_M)

Überseh ich was? Die ersten Element werden jeweils auf max gesetzt, bis 
N erreicht ist (das letzte davon evtl kleiner als max), die restlichen 
auf 0.

foo(float arr[], float max[], float n, int m)
{
    for (int i = 0; i < m; ++i)
    {
        arr[i] = max[i] < n ? max[i] : n;
        n -= arr[i]; // rounding ...
    }
}

[Mario M. (thelonging)]

asdfasd schrieb:
> Überseh ich was?

Ja, das "zufällig" in der Überschrift. ;-)

[Peter (Gast)]

Ich würde erst allgemein alle Lösungen berechnen um eine Zahl in N Teile 
zu zerlegen und dann zufällig eine der Lösungen auswählen.

Das mathematische Problem kommt aus dem Bereich der Zahlkompositionen. 
Einen einfachen Ansatz findest du hier: 
http://www.aconnect.de/friends/editions/computer/combinatoricode_g.html
unter "2.2.3. k-Partitionen mit Berücksichtigung der Reihenfolge, 
kolexikographisch geordnet".
Allerdings ohne Maximalwert und mit 1 beginnend. Habe den Algorithmus 
selbst so wie du ihn möchtest darauf aufbauend auch gebraucht und ihn 
letzlich in LabVIEW implementiert. C/C++ kann ich dir nicht anbieten.

[Georg (Gast)]

asdfasd schrieb:
> Überseh ich was?

Mario M. schrieb:
> Ja, das "zufällig" in der Überschrift. ;-)

Die Forderung ist, wie sich nach und nach herausstellt, noch schärfer: 
die Zahlen sollen nicht nur zufällig, sondern auch statistisch 
gleichverteilt sein. Natürlich ist das nur begrenzt sinnvoll, wenn man 8 
in 4 Teile teilen will wird man keine Gleichverteilung hinkriegen.

Mike M. schrieb:
> 3) jeder Teil darf maximal einen jeweils für jeden Teil separat
> definierten Wert annehmen (max_1, ..., max_M)

Wozu lauter verschiedene Grenzen? Das macht eine Lösung in fast allen 
denkbaren Fällen unmöglich. Man kann ja sagen, so darf man die Werte 
halt nicht wählen, aber das ist ja kein anwendbarer Algorithmus.

Georg

[Vlad T. (vlad_tepesch)]

warum nicht für jedes feld einen zufälligen wert zwischen 0 und dem 
jeweiligen Maximum ermitteln?
Anschließend wird die Summe der Einzelteile auf die gesuchte Zielsumme 
skaliert.

Soll die Lösung aus ganzen Zahlen bestehen wird in diesem Schritt 
jeweils abgerundet und der Rest auf eine zufällige Zahl aufaddiert 
(wobei natürlich das maximum beachtet wird)


Edit:

code:

#include <iostream>
#include <vector>
#include <random>
#include <iterator>



template <typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

int main()
{
  // general parameter
  const int minNumbers = 3;
  const int maxNumbers = 10;
  const float minPart = 2;
  const float maxPart = 1000;

  // problem variables
  int   numbers;
  float targetSum;
  std::vector<float> maxValues;

  std::mt19937 rng;
  rng.seed(std::random_device()());


  // init problem
  numbers = std::uniform_int_distribution<>(minNumbers, maxNumbers)(rng);
  targetSum = 0;
  maxValues.resize(numbers);
  for (auto& v : maxValues) {
    v = std::uniform_real_distribution<float>(minPart, maxPart)(rng);
    targetSum += v;
  }
  targetSum = std::uniform_real_distribution<float>(minPart, targetSum)(rng);

  std::cout << "tartet sum: " << targetSum << " maxvalues: " << maxValues << std::endl;




  // solve
  std::vector<float> values(maxValues);
  float valuesSum = 0;

  float sumCheck = 0;

  for (auto& v : values){
    v = std::uniform_real_distribution<float>(0, v)(rng);
    valuesSum += v;
  }

  std::cout << "random vec: sum: " << valuesSum << " values: " << values << std::endl;

  for (auto& v: values)
  {
    v *= targetSum / valuesSum;
    sumCheck += v;
  }
  std::cout << "output vec: sum: " << sumCheck << " values: " << values << std::endl;



  return 0;
}