Question

How to generate N random 1s in a zero-based matrix with Pascal

Answer 1

program RandomMatrixOnes;

{$mode objfpc}{$H+}{$J-} // Use modern Object Pascal dialect, Ansistrings, and read-only constants

uses
  SysUtils;

type
  // Define a 2D dynamic array for the matrix
  TMatrix = array of array of Integer;

{
  Creates and initializes a Rows x Cols matrix with zeros, 
  then randomly distributes exactly NumberOfOnes '1's using 
  Fisher-Yates (Knuth) sampling to avoid infinite loops and collisions.
}
function GenerateRandomOnesMatrix(const Rows, Cols, NumberOfOnes: Integer): TMatrix;
var
  TotalCells, i, SelectionIndex, Temp: Integer;
  FlatIndices: array of Integer;
  R, C: Integer;
begin
  TotalCells := Rows * Cols;

  // Guard against invalid inputs using standard SysUtils exceptions
  if (Rows <= 0) or (Cols <= 0) then
    raise EArgumentException.Create('Matrix dimensions must be positive.');
  if (NumberOfOnes < 0) or (NumberOfOnes > TotalCells) then
    raise EArgumentException.Create('NumberOfOnes exceeds available matrix cells.');

  // Explicitly initialize managed Result variable to suppress compiler warning
  Result := nil;

  // Initialize the 2D dynamic array to 0s
  SetLength(Result, Rows, Cols);
  for R := 0 to Rows - 1 do
    for C := 0 to Cols - 1 do
      Result[R][C] := 0;

  if NumberOfOnes = 0 then
    Exit;

  // Build a flat array representing continuous linear indices [0 .. TotalCells - 1]
  SetLength(FlatIndices, TotalCells);
  for i := 0 to TotalCells - 1 do
    FlatIndices[i] := i;

  { 
    Partial Fisher-Yates Shuffle:
    Randomly select NumberOfOnes unique flat positions in O(N) time complexity.
    This guarantees uniform distribution without repetitive collision retries.
  }
  for i := 0 to NumberOfOnes - 1 do
  begin
    // Select a random index from the remaining unchosen pool
    SelectionIndex := i + Random(TotalCells - i);

    // Swap selected element into the prefix position 'i'
    Temp := FlatIndices[i];
    FlatIndices[i] := FlatIndices[SelectionIndex];
    FlatIndices[SelectionIndex] := Temp;

    // Map the 1D linear index back to 2D coordinates (Row, Col)
    R := FlatIndices[i] div Cols;
    C := FlatIndices[i] mod Cols;

    Result[R][C] := 1;
  end;
end;

{
  Utility procedure to display the matrix contents on standard output.
}
procedure PrintMatrix(const Matrix: TMatrix);
var
  R, C, Rows, Cols: Integer;
begin
  Rows := Length(Matrix);
  if Rows = 0 then Exit;
  Cols := Length(Matrix[0]);

  for R := 0 to Rows - 1 do
  begin
    for C := 0 to Cols - 1 do
      Write(Matrix[R][C]:2, ' ');
    WriteLn;
  end;
end;

var
  Matrix: TMatrix;
  Rows, Cols, NumberOfOnes: Integer;
begin
  // Initialize standard PRNG seed
  Randomize;

  Rows := 5;
  Cols := 7;
  NumberOfOnes := 10;

  WriteLn(Format('Generating a %dx%d matrix with %d random 1s:', [Rows, Cols, NumberOfOnes]));
  WriteLn;

  try
    Matrix := GenerateRandomOnesMatrix(Rows, Cols, NumberOfOnes);
    PrintMatrix(Matrix);
  except
    on E: Exception do
      WriteLn('Error: ', E.Message);
  end;
end.



{
run:

Generating a 5x7 matrix with 10 random 1s:

 0  0  1  1  0  1  0 
 0  0  0  0  1  0  1 
 0  1  0  1  0  0  1 
 1  0  0  0  0  0  0 
 0  0  0  1  0  0  0 

}

 

70+ SQL courses for beginners and professionals