0
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

int main(void){
  int num[] = {1, 1, 2, 2, 3, 3}; // Given array which has to be shuffled
  int swap;
  int i, j;

  srand(time(NULL));

  for(i = 1; i < 6; i++){ // Start of Fisher Yates Shuffle
    j = rand() % (i + 1);

    if(j != i){
      swap = num[j];
      num[j] = num[i];
      num[i] = swap;
    }

  } // End of FISHER-YATES


  // Printing the array
  printf("\nThe array is [ ");
  for(i = 0; i < 6; i++){
    printf("%d ", num[i]);
  }
  printf("]");

}

[Edited]: {Since a lot of you requested further clarification in the question, I am editing the question to make things clearer. Changes Made:

  1. Use of "equal" instead of similar in line-3(Paragraph 1)

  2. By spacing of 2, I mean that a number can appear again only after 2 other different numbers have appeared after it. (For example, [3, 1, 2, 3, 1, 2] is a correct output while [3, 1, 3, 2, 1, 2] is incorrect) And the spacing has to be "at least 2".

  3. Use of word "different/ unequal" in line-4(Paragraph 2) }

I tried placing counters to check the 2 indexes ahead of the current value of the array and choose to shuffle or not shuffle based on the value at that index being "equal" or not "equal" to the number being shuffled.

What I am trying to do is make a general program that can similarly take in 'n' "distinct" values and shuffle with a constraint or spacing of maximum 'n-1' (Because for example, to have a spacing of 3 between same elements you need minimum 3 other "different/ unequal" elements in the array, therefore there need to be at least 4 distinct elements for a spacing of 3 between equal numbers).

Hope this helps you to understand what I'm trying to say.

  • (a) The only arrangements that have all duplicates spaced exactly two elements apart have the pattern ABABCDCDEFEF…. This is because whatever the first element, A, is, to be spaced two apart, the third element must also be A, and then the second element, B, must be repeated at position four, and then this repeats. You can easily implement a random draw of such a pattern by doing a Fisher-Yates shuffle to form ABCD… and then using that to write ABABCDCD… (Or, by spacing of two, do you mean two elements between duplicates, not a distance of two from one to the other? A similar result applies.) – Eric Postpischil Feb 25 '23 at 18:01
  • I'm not understanding what you mean by "spacing of 2" exactly. To detect dups, I'd sort the array. But, given a slightly different array: `1 2 3 4 5 5 6 7 8`, what would be okay? `8 2 1 5 7 5 6 4 3` and/or `8 2 1 5 7 6 4 3 5`? Perhaps specifying several input arrays and some of the acceptable output arrays may help. Note that [AFAIK] true randomness allows long strings of dups. I think a clearer explanation of the additional rules would help. Please edit your question – Craig Estey Feb 25 '23 at 18:01
  • (b) What does “similar” mean? – Eric Postpischil Feb 25 '23 at 18:01
  • (c) Re “to have a spacing of 3 between same elements you need minimum 4 other elements in the array”: How do you figure that? With ABCDA, there are three elements between the two As but there are only three elements other than A, not four. – Eric Postpischil Feb 25 '23 at 18:03
  • (d) Re “maximum 'n-1'”: So the require spacing is not two elements or three or some fixed number but can vary up to some maximum? – Eric Postpischil Feb 25 '23 at 18:05
  • Start from scratch and clarify the whole question. Let n be the number of elements. I suspect you want to generate a permutation of elements such that the maximum distance between one occurrence of a value and the next is at most n. (That is distance, so adjacent elements are one unit apart; it is not the number of elements between the two occurrences.) How long is the permutation? 2n elements? Longer? Does every value have to repeat the same number of times? If we have 1222222…, does that satisfy the requirements because the distance between any value and its next occurrence is at most one? – Eric Postpischil Feb 25 '23 at 18:08
  • The only thing that's unclear about the question is when you say "a spacing of 2", do you mean "a spacing of exactly 2" or "at most 2" or "at least 2". Otherwise the question seems very clear to me. – Stef Feb 26 '23 at 00:03
  • @Stef: Since you understand the question clearly, please edit answers and clarifications to the questions and issues in comments above into the question. – Eric Postpischil Feb 26 '23 at 01:11
  • @EricPostpischil I have edited the question and tried to clarify most of your doubts. Hope this helps! Please let me know if any further clarification is required. – Nikhil Vishnoi Feb 26 '23 at 21:22
  • 1
    @Stef : The spacing is of "at least 2" – Nikhil Vishnoi Feb 26 '23 at 21:24
  • Does the array to be shuffled have exactly two of each element? – Eric Postpischil Feb 27 '23 at 01:22
  • @EricPostpischil: Yes it can only have exactly 2 of each element. – Nikhil Vishnoi Feb 28 '23 at 21:37
  • Then the only solution is the n elements appear once in any order, and then they appear again in exactly the same order. Proof: Let A be the element in position 0. Then it must next at position n or greater. If it is greater, then the element at position n must duplicate one of the elements in positions 1 to n−1, but it would be too close. So the second A must be at position n. Similarly, the element at position 1 must appear at n+1, and so on. So the solution is to generate a shuffle of the n elements in the first n positions and then copy it. – Eric Postpischil Feb 28 '23 at 21:48
  • @EricPostpischil I think you and I understood the problem differently. Consider n=4, initial list = `[1,1,2,2,3,3,4,4]`, shuffled list = `[3, 1, 4, 3, 2, 1, 4, 2]`? The shuffled list appears to be a correct solution. It correctly has every element separated by at least 2. Yet it does not satisfy your constraint "the n elements appear once in any order, and then they appear again in exactly the same order". – Stef Mar 01 '23 at 11:10
  • 1
    @Stef: The question currenty states that when there are n distinct values, the constraint is to have n−1 elements between repeated values. Then 3, 1, 4, 3, 2, 1, 4, 2 does not satisfy the constraint because n is 4 but there are only 2 elements between the two 3s. The “2” in the title is from the original example with n=3 and has not been updated to match the other edits OP made. – Eric Postpischil Mar 01 '23 at 11:19
  • Oooooooh indeed – Stef Mar 01 '23 at 11:21

0 Answers0