[ALGORITMO] : calcolo delle somme possibili dato un risultato conosciuto

[oureyes]

ma infatti ti ringrazio comunque, solo per aver letto e provato a pensarci.

inoltre ho anche trovato tutto l'algoritmo già scritto in C, peccato che debba tradurlo in PHP e che non sappia una mazza di C.

se a qualcuno puo interessare lo posto volentieri.

[ESSE-EFFE]

Io, grazie anche ai suggerimenti di Krek_Stealth, un algoritmo che pare funzionare l'ho trovato.

Abbiamo in input il risultato finale (Somma) e il numero di addendi (Addendi).

Tralasciando casi limite (solo un addendo o risultato inferiore al numero di addendi), si tengano i numeri in un array Arr di dimensione Addendi (ovviamente).

Per comodità definiamo l'indice limite di questo array come IndexMax pari a Addendi - 1.

Si parte dalla condizione in cui Arr[0] è pari a Somma - IndexMax e Arr[1..IndexMax] pari a 1.
Questa è la prima combinazione valida.

Per trovare le altre combinazioni, basta un ciclo I che va da IndexMax a 1. Per ogni valore di I si deve controllare se Arr[I - 1] è maggiore di (Arr[I] + 1).

Se la condizione è verificata, allora:

1) si procede alla distribuzione facendo:
Arr[I - 1] = Arr[I - 1] - 1
e
Arr[I] = Arr[I] + 1

2) si è trovata un'altra combinazione valida e va verificata di nuovo la condizione iniziale.

Altrimenti non ci sono altre combinazioni.

A questo ciclo sfugge talvolta una combinazione in un caso particolare, vale a dire nel caso in cui Somma sia divisibile per Addendi (ad esempio se Somma è 9 e Addendi è 3 la combinazione 3, 3, 3 non viene generata). Per aggirare il problema basta un semplice controllo alla fine:

Se Somma è divisible per Addendi e Arr[0] non è uguale a (Somma / Addendi) allora si aggiunge la combinazione in cui Arr[0..IndexMax] è pari a (Somma / Addendi).

Ovviamente ho anche scritto un programma in C per testare e facendo qualche prova sembra che funzioni. Comunque se vuoi postare l'algoritmo "ufficiale" può essere utile. Spero di non aver fatto errori nel riportare il tutto.

HTH,

[oureyes]

questo è il codice C trovato :

#include<stdio.h>
#include<stdlib.h>
#define false 0;
#define true 1;
#define Min(x,y) ((x<y)?x:y)
  
typedef struct partitionnode 
{
    int m;
    int numparts;
    int parts[101];
} partition;

void output(partition a)
/*
**  print out the partition a
*/
{
 int i,j;
 printf("%d = ",a.m);
 for(i=1;i<=a.numparts;i=i+1)
 {
    j = a.parts[i];
    printf("%d",j);
    if (i != a.numparts)
      printf("+");
 }
}

void PartitionLexSuccessor(int m,int n,partition *a,int *flag)
/*
**  Algorithm 3.7
**  replaces the partition a by its successor,
**  where a is given in standard form
*/
{
  int i,j,d;

  i =  2;
  while( (i<=n) && ((*a).parts[1]<=((*a).parts[i]+1)) )
    i=i+1;
  if(i == (n+1))
  {
    *flag = false;
  }
  else
  {
     (*a).parts[i] = (*a).parts[i] + 1;
     d = -1;
     for(j=(i-1);j>=2;j=j-1)
     {
         d = d + (*a).parts[j] - (*a).parts[i];
         (*a).parts[j]  =  (*a).parts[i];
     }
     (*a).parts[1] =  (*a).parts[1] + d;
  }
}

int main()
{ 
  int m,n,i,j,r,s,num;
  int flag;
  partition a;
  char junk;
  

  m = 10;
  n = 4;
  printf("Test of Algorithm 3.7 with m=%d n=%d \n\n",m,n);
  a.m = m;
  a.numparts = n;
  a.parts[1] =  m-n+1;
  for(i=2;i<=n;i=i+1)  
    a.parts[i] = 1;
  flag =  true;
  while(flag)
  {     
     output(a);
        
     PartitionLexSuccessor(m,n,&a,&flag);     
  }
  printf("\nEnd of test. \n"); 
  
  return(0);
}

la variabile m dichiarata in main equivale al risultato e
la variabile n dichiarata in main equivale al numero degli addendi.

compilato e provato . funziona.

siccome devo tradurla in linguaggio PHP fino ad un certo punto riesco ad intepretarlo, ma ci sono alcuni passaggi che non mi sono chiari

come ad esempio, cosa sta a significare questo codice :

typedef struct partitionnode 
{
    int m;
    int numparts;
    int parts[101];
} partition;

e soprattutto la dichiarazione "partition a" posta nella funzione main, e richiamata nelle altre funzioni.

qualcuno ha dimestichezza con il C ?

[ESSE-EFFE]

questo è il codice C trovato :

Sì, vero, con il procedimento che ho scritto io non si trovano tutte le combinazioni. Il controllo come vedi è simile, solo che non va fatto solo tra Arr[I] e Arr[I - 1], ma tra Arr[I] e tutti gli addendi che precedono (o viceversa). Così si evita anche il controllo finale tra l'altro.

siccome devo tradurla in linguaggio PHP fino ad un certo punto riesco ad intepretarlo, ma ci sono alcuni passaggi che non mi sono chiari

come ad esempio, cosa sta a significare questo codice :

typedef struct partitionnode 
{
    int m;
    int numparts;
    int parts[101];
} partition;

E' la definizione di una struttura. Puoi anche farne a meno e dichiarare una variabile per ogni membro.

[oureyes]

posto il codice in PHP se dovese servire a qualcuno. e ringrazio tutti per il supporto datomi fino a qui.

function output($a)
{
 printf($a["m"]." = ");
 for($i=1;$i<=$a["numparts"];$i=$i+1)
 {
    $j = $a["parts"][$i];
    printf($j);
    if ($i != $a["numparts"])
      printf("+");
 }
 echo "
";
}
function PartitionLexSuccessor($m,$n,&$a,&$flag)
{
  	$i =  2;
	while( $i<=$n && ($a["parts"][1]<=($a["parts"][$i]+1)))
  		$i=$i+1;
	if($i == ($n+1))
	{
		$flag = false;
	}
	else
	{
		$a["parts"][$i] = $a["parts"][$i] + 1;
		$d = -1;
		for($j=($i-1);$j>=2;$j=$j-1)
		{
			$d = $d + $a["parts"][$j] - $a["parts"][$i];
			$a["parts"][$j]  =  $a["parts"][$i];
		}
		$a["parts"][1] =  $a["parts"][1] + $d;		
	}
}
$m = 10;
$n = 4;

$a=array();
$a["m"] = $m;
$a["numparts"] = $n;
$a["parts"]=array();
$a["parts"][1] =  $m-$n+1;
$flag=true;  
for($i=2;$i<=$n;$i=$i+1)  
  $a["parts"][$i] = 1;
do{
     output($a);
     PartitionLexSuccessor($m,$n,$a,$flag);  
    } while ($flag);

[Krek_Stealth]

Sul fatto invece che siano un paio di cicli, dove a ogni passaggio che si toglie uno dal primo numero si ridistribuisca il tolto fra gli altri numeri , non mi sembra molto corretto; basti pensare solo che il numero del primo addendo di ogni combinazione non è sempre detto che sia un numero inferiore al precedente.

LoL

se la combinazione 4 3 1 è uguale alla 3 4 1 o alla 1 3 4

e proprio una ridistribuzione in cui il primo addendo è il maggiore possibile, al momento che non lo fosse più vorrebbe dire che la combinazione che abbiamo dopo esiste già.

6 1 1
5 2 1
4 3 1
4 2 2
3 3 2
3 4 1 ops --- esiste già (4 3 1)
1 3 4 ops --- esiste già (4 3 1)
etc.
---------------------------------
3 3 2 è il caso in cui il secondo addendo è uguale al primo ma come vedi 3 resta cmq il maggiore.

Cmq son contento che abbiate trovato la soluzione.

Buon Proseguimento

P.S.: Appena ho tempo testo il codice che hai postato ciao e bon lavoro.