How to fill a two-dimensional array with the specified percentage of filling?

For example, there is an array of 10 * 10, it is necessary to fill 30% of the cells in it, therefore, 30 cells will contain data, 70 will be empty.

The task arose as a result of solving another, larger problem, therefore, I publish the entire code below. Array Generator Method - generateData

I have three solutions.

The first solution is to recursively call a function that bypasses the array and gradually fills the empty cells with data. We start with the zero element of the array, if we have not reached the fill number, we call the function again. The disadvantage is that the recursive approach itself is not very good and the filled cells get stuck on one side. A possible solution is to reach the end of the array in the opposite direction.

 const getStyle = style => Object.assign({}, style); const universeStyle = length => ({ position: "relative", width: `${length * 10}px`, height: `${length * 10}px`, fontSize: "0", border: "1px solid #222" }); const cellStyle = item => ({ background: `${item.color}`, display: "inline-block", boxSizing: "border-box", width: "10px", height: "10px" //border: "1px solid grey" }); const settingsStyle = () => ({ margin: "10px 0 0 0" }); const Cell = ({ item }) => ( <div x={item.x} y={item.y} style={getStyle(cellStyle(item))} /> ); class Universe extends React.Component { render() { return ( <div style={getStyle(universeStyle(this.props.width))}> {this.props.data.map(item => item.map(item => <Cell item={item} />))} </div> ); } } class Settings extends React.Component { render() { const {fill} = this.props; return ( <div style={getStyle(settingsStyle())}> <button onClick={() => this.props.generateUniverse()}>Generate</button> <div> <input onChange={event => this.props.setFill(event)} type="range" value={fill} /> <span>{fill}</span> </div> </div> ) } } class App extends React.Component { constructor(props) { super(props); this.state = { data: [], fill: 30 }; } componentDidMount() { this.generateUniverse() } getColor(colors = ['white', 'black']) { return colors[Math.floor(Math.random() * colors.length)]; } generateData(width, fill) { const count = (width * width * fill) / 100; const getColor = this.getColor; let current = 0; const spaceData = Array.from({ length: width }).map((item, y) => Array.from({ length: width }).map((item, x) => ({y: y, x: x, color: 'white'}) )) function fillData(data) { if (current < count) { data.forEach((line, y, data) => line.forEach((obj, x, line) => { if (current < count) { obj.color = getColor(); obj.color === 'black' ? current++ : null; } else { return data } }) ) return fillData(data) } return data } return fillData(spaceData) } generateUniverse() { this.setState({ data: this.generateData(this.props.width, this.state.fill) }); } redrawUniverse() { const idRedraw = setTimeout(() => { this.setState({ data: this.generateData(this.props.width) }, this.redrawUniverse); }, 500); this.idRedraw = idRedraw; } stopRedraw() { clearTimeout(this.idRedraw) } setFill(event) { console.log(event.target.value) this.setState({fill: event.target.value}) } render() { const [{width}, {data, fill}] = [this.props, this.state]; return ( <div> <Universe width={width} data={data} /> <Settings fill={fill} setFill={(event) => this.setFill(event)} stopRedraw={() => this.stopRedraw()} startRedraw={() => this.redrawUniverse()} generateUniverse={() => this.generateUniverse()} /> </div> ) } } ReactDOM.render(<App width={10} />, document.body); 
 <script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react-dom.min.js"></script>

The second solution is to randomly generate the X, Y coordinates of each point; if the required point in the array is already filled — skip, if not, fill. The process is repeated until the array reaches the fill. The disadvantage is that at large percentages of filling, we will have few empty points and the program will spend more time searching for an empty value.

 const getStyle = style => Object.assign({}, style); const universeStyle = length => ({ position: "relative", width: `${length * 10}px`, height: `${length * 10}px`, fontSize: "0", border: "1px solid #222" }); const cellStyle = item => ({ background: `${item.color}`, display: "inline-block", boxSizing: "border-box", width: "10px", height: "10px" }); const settingsStyle = () => ({ margin: "10px 0 0 0" }); const Cell = ({ item }) => ( <div x={item.x} y={item.y} style={getStyle(cellStyle(item))} /> ); class Universe extends React.Component { render() { return ( <div style={getStyle(universeStyle(this.props.width))}> {this.props.data.map(item => item.map(item => <Cell item={item} />))} </div> ); } } class Settings extends React.Component { render() { const {fill} = this.props; return ( <div style={getStyle(settingsStyle())}> <button onClick={() => this.props.generateUniverse()}>Generate</button> <div> <input onChange={event => this.props.setFill(event)} type="range" value={fill} /> <span>{fill}</span> </div> </div> ) } } class App extends React.Component { constructor(props) { super(props); this.state = { data: [], fill: 30 }; } componentDidMount() { this.generateUniverse(); } getRandom(data) { return data[Math.floor(Math.random() * data.length)]; } generateData(width, fill) { const countFillObj = (width * width * fill) / 100; var currentFillObj = 0; const getRandom = this.getRandom; const arr = Array.from(Array(width).keys()); const data = Array.from({ length: width }).map((item, y) => Array.from({ length: width }).map((item, x) => ({y: y, x: x, color: 'white'}) )) if (fill === 100) { return Array.from({ length: width }).map((item, y) => Array.from({ length: width }).map((item, x) => ({y: y, x: x, color: 'black'}) )) } while (currentFillObj < countFillObj) { var [randomX, randomY] = [getRandom(arr), getRandom(arr)]; var currentObj = data[randomX][randomY]; if (currentObj.color === 'white') { currentObj.color = 'black'; currentFillObj += 1 } } return data } generateUniverse() { this.setState({ data: this.generateData(this.props.width, this.state.fill) }); } redrawUniverse() { const idRedraw = setTimeout(() => { this.setState({ data: this.generateData(this.props.width) }, this.redrawUniverse); }, 500); this.idRedraw = idRedraw; } stopRedraw() { clearTimeout(this.idRedraw) } setFill(event) { this.setState({fill: event.target.value}); this.generateUniverse(); } render() { const [{width}, {data, fill}] = [this.props, this.state]; return ( <div> <Universe width={width} data={data} /> <Settings fill={fill} setFill={(event) => this.setFill(event)} stopRedraw={() => this.stopRedraw()} startRedraw={() => this.redrawUniverse()} generateUniverse={() => this.generateUniverse()} /> </div> ) } } ReactDOM.render(<App width={10} />, document.body); 
 <script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react-dom.min.js"></script>

The third solution appeared while writing a question, you can try to enter a correction factor in the probability of filling. And when traversing an array, when a point is filled / skipped, the probability of the next points filling / skipping changes.

Share, please, ideas

  • The two-dimensional array is perfectly linearized: a(x,y) => b(x*n+y) and, accordingly, de-linearized. So in fact, the task is reduced to the generation of a given number (z%) of non-repeating random integers in a given range, and this is a very standard task. - Akina
  • @Akina did not understand the answer. I don't need random numbers. need 1 or 0. - while1pass
  • Well, you read it, yes ... random numbers give you the "coordinates" of the next one in the array. - Akina
  • @Akina "get a handle on" the second solution ... just randomly generating coordinates. there also indicated a lack of such a solution. Are there links to solving a "standard" problem? - while1pass
  • 1) Random generation of coordinates separately can rest against the generator "features", which will give a cluster distribution; 2) You yourself point to the problem of re-hitting the same element. - Akina

2 answers 2

It is necessary to count the number of already filled cells, and on the basis of it, calculate the probability of filling the next one.

Like that:

 var k = n * n * 0.3, // оставшееся количество заполненных клеток r = n * n; // оставшееся количество клеток for (var i = 0; i<n; i++) { for (var j = 0; j<n; j++) { if (Math.random() < k/r) { a[i][j] = 1; k--; } else { a[i][j] = 0; } r--; } }

This algorithm makes all possible fill options equally likely.

  • Yes thank you! at first glance, what you need. it was all pretty simple. have flaws? - while1pass
  • @ while1pass yes it seems no. - Pavel Mayorov

Simple, though not the best, algorithm.

  1. Create a temporary two-dimensional array tmp (n * m - 1, 1). In the first dimension, the number is equal to the number of elements in the finite array n * m, in the second dimension it is 2.

  2. tmp (i, 0) = i; tmp (i, 1) = rand ();

  3. Sort by the second dimension.

  4. We take the desired percentage of the first elements, determine the coordinates (x = tmp (i, 0) \ n, y = tmp (i, 0)% n) by the value of the first dimension and set the value (array (x, y) = 1).

  5. Done

  • Sorting is one of the most resource-intensive operations. At paragraph 3, it is not clear what we are sorting and why? What is the array at this point? - while1pass
  • Yes, expensive. But with 100 elements (and most likely interactive work) this is not so important. In p. 3 we sort by random value. - Akina