Array with at most n duplicates

Hey all this is my first post on cprogramming.com as I am fairly new at C++.
I am taking a programming class and we were given an assignment that I am having trouble with.
1. The object of the assignment is to have an array of size n of random integers between x- z. (I have this part)
2. I am to create a new (dynamically allocated) array from the original with at most n duplicate values WITHOUT SORTING FIRST. (this is the part I am having trouble with)

I have tried moving the unwanted duplicates to the end and then ignoring them but I couldn't make it work.
I have tried using a temporary array of flags where unwanted duplicates are flagged as zero but couldn't make that work either.

I am having a real problem with the logic of this assignment.
I could really use a good algorithm in pseudocode for dynamically creating the second array with at most n duplicates.

Million thanks in advance,
kratz

It's a little unclear to me what the second requirement of your assignment is. Do you mean there may be at most n duplicates for each value or do you mean there may be a total of no more than n duplicates in the entire array?

well, go through them, and count the duplicates. when you know how many original numbers you have, create a new array with that amount, and fill it in...

Maybe something like:

Make empty map: element mapped to count
Loop through each element in initial array
-- Find element in map, increment count
-- If count is less than maximum duplicates
-- -- Insert into new array

Lucky and everyone else.

Thanks for replying. I'm sorry if I was unclear. The new array can have at most n duplicates of each item. For example:

Array 1 (cannot be sorted)
19 16 17 18 17 15 16 18 17 19 20 16 15 18 15

Array 2 (with 2 duplicates of each item allowed)
15 16 17 18 15 16 18 17 19 20 19

I dont know about the map container, would Daved's suggestion still work?

I'm assuming this suggestion works (I havent tried). I guess you could put the values in a linked list 1 by 1 which checks if the node's int is equal to value (if it is, then it increments the count if count < 2, if its == 2 then it ends the search), if it isnt then it checks the next node. If it checks all nodes and none equal, then it puts the number in its own next free node. The result is each node contains its own value, and a count int for each node saying how many numbers each.

Code:

---

Node1->number = 19, Node1->count = 2;
Node2->number = 16, Node1->count = 1;

---

You can then export the values using another linked list function into the new array and it will output exactly how you've showed in your last post.

However, this solution may fall under "sorted" (even though it doesnt sort by value), and its quite an extreme solution at that.. lots of code, for such a problem. You'd assume theres a different and much easier way.

Thanks for the help but that's not quite what I need.

The thing is we aren't using STL containers or linked lists because we haven't gotten to them yet. Basically the algorithm has to use just a plain array.
This really has me stumped..........it would be so much easier to work with a sorted array.........

well I don't know how efficient this method would be but it should work

Code:

---

allocate space for all elements in the array
for ( i = 0; i < length of array; i++ )
{
    for ( j = 0; j < # of items in array 2; j++ )
    {
        if item i of array == item j of array 2
            increment duplicate item count for item i
    }
    if we have duplicate items
        do whatever
    else
        do whatever
}
realloc j so it is just large enough for the number of valid items it contains

---

id just take the first array, sort it, then compare the next
item in the array to the last one, if it the same keep it,
but if the one after that is the same, then i just wouldnt add
it to my next array. when using the array btw be careful not
to overstep it bounds.

I am not allowed to sort the first array

So don't sort it first. Just go like so:

Code:

---

for each element in the old array
    copy this element over
    for each element in the old array that has the same value as this one
        copy this element if we have less than N (use a simple counter)
        mark this cell as "unused" by setting it to some value not in the array

---

That's the basic idea. If it's marked "unused", skip it when you're processing the outer loop.


Quzah.

Quote:

---

Originally Posted by quzah

So don't sort it first. Just go like so:

Code:

---

for each element in the old array
    copy this element over
    for each element in the old array that has the same value as this one
        copy this element if we have less than N (use a simple counter)
        mark this cell as "unused" by setting it to some value not in the array

---

That's the basic idea. If it's marked "unused", skip it when you're processing the outer loop.


Quzah.

---

This turns:

Quote:

---

Array 1 (cannot be sorted)
19 16 17 18 17 15 16 18 17 19 20 16 15 18 15

I believe into Array 2 (with 2 duplicates of each item allowed)
19 19 16 16 17 17 18 18 15 15 20 //only two of each, but mixed up, and now in pairs

---

It sorts it in pairs, but not by number, which is like the best you can get. If you wanted:

Quote:

---

Array 1 (cannot be sorted)
19 16 17 18 17 15 16 18 17 19 20 16 15 18 15

into: Array 2 (with 2 duplicates of each item allowed)
19 16 17 18 17 15 16 18 19 20 15 //only two of each, and in order

---

That would ignore values in the array after there have been more than n of them, and it does it in order. That would require 2 copies of the array, old and new, a static counter array that you can align with a static temp array that you assign the old value to and with if statements you wont have more than 1 of each value in the temp array, or more than n values in the new array. The problem is 1) figuring out how to do it, 2) it requires like 4 if statements and 3-4 loops, hah.

He didn't say it couldn't be sorted while you do the copying. He said you can't sort it first. I'm not sorting it first. I'm simply copying pairs as I run across them.


Quzah.

Quote:

---

Originally Posted by quzah

He didn't say it couldn't be sorted while you do the copying. He said you can't sort it first. I'm not sorting it first. I'm simply copying pairs as I run across them.


Quzah.

---

Oh yeah thats definetly legit.

But just incase theres extra qaulifications. I made the modified version of what quzah had that will do it all in order as said in my last post.

I could post the actual code, since this guy seems to understand and care about it.. but the community may freak out if I post actual working code in an assignment post. So..

Code:

---

initialize the int old array
define the int maxOfNum
define three letter variables to work with the three loops

define the int new array, doesnt need values (same size as old array)
define the int static temp array, doesnt need values (same size as old array)
define the int static countOfNum, that is used to align with the temp array to see how many of each number have been copied to the new array

outer for loop looks at every element in old array, use < (element amount)
  inner for loop looks at every element in temp array, but use <= (element amount) so theres 1 extra
    if the index variable is equal to the last number possible in the for loop,
      another inner for loop looks for a temp array element thats not used, use < (element amount)
        apply the element of this loop of the temp array to the outer loop element of the old array
        apply the element of the outer loop of the new array to the outer loop element of the old array
        increment the countOfNum by 1
        break out of the loop because you've assigned the value
      break out of this loop too becaus you've assigned the value
    else if the temp array value is equal to the old array value (this checks to see if the number already exists in temp array)
      if the countOfNum is less than the maxOfNum
        apply the element of the outer loop of the new array to the outer loop element of the old array
        increment the countOfNum by 1
      break out of the loop because you've assigned the value
  print the new array at the end of the outer loop

---

It also leaves for expansion because with that it just wont copy the value from old array to new array, but since you already made new array with the same size as old array, its going to have blank spots, which will not be set. So if you used it you'd have to do what quzah said just like with his and set it to an undefined value and figure out how to get rid of that after its processed.

It's actually even easier than that.

Code:

---

for each element in the array
    count occurances of this number in the new array
    if count less than N, copy this over to the new array

---

That's all folks.


Quzah.

Quote:

---

Originally Posted by quzah

It's actually even easier than that.

Code:

---

for each element in the array
    count occurances of this number in the new array
    if count less than N, copy this over to the new array

---

That's all folks.


Quzah.

---

:eek: Awesome, I had to define the count as static (since the value assigned to it would go away after the count occurances loop ended) and set it to 0 at the beginning of the outer loop.. but it works! /clap

Thanks for everyone's help. Based on everyone's responses, I have some semi-working code.

Code:

---

//Pass in 2 arrays of same size
//1 filled with random numbers other with zeros

int copies, new_size = 1;

*(array2 + 0) = *(array1 + 0);

for (int i = 1; i < size1; i++)
{
    copies = 0;    //Reset count to 0
    for (int j = 0; j < size1; j++)
    {
        if (*(array1 + i) == *(array2 + j))
          copies++;
    }
   
    if (copies < max_dups)    //Max_dups is a constant
    {
      *(array2 + i) = *(array1 + i);
      new_size++; 
    }

}

---

This code gives me a new array with zeros in the unwanted slots.

The thing I don't like about this code is that I would rather have the new array be dynamically allocated based on new_size.

Obviously this code wouldn't work if I wanted to include zeros in my set of random numbers.

I hope I am making sense to everyone and again thanks a bunch for the help.

kratz

Code:

---

#include <cstdio>
#define N 2
size_t countin( int n, int array[], size_t size )
{
    size_t ret = 0;
    for( size_t x = 0; x < size; x++ )
        if( array[ x ] == n )
            ret++;
    return ret;
}

int main( void )
{
    int array[] = { 1, 3, 4, 5, 2, 3, 4, 1, 3, 4, 4, 3, 4, 2 };
    int newarray[ sizeof array / sizeof array[ 0 ] ] = {0};
    size_t x, y;

    for( y = x = 0; x < sizeof array / sizeof array[ 0 ]; x++ )
        if( countin( array[ x ], array, y ) < N )
            newarray[ y++ ] = array[ x ];

    for( x = 0; x < y; x++ )
        printf("newarray[ %d ] is %d\n", x, newarray[ x ] );

    return 0;
}
/*
newarray[ 0 ] is 1
newarray[ 1 ] is 3
newarray[ 2 ] is 4
newarray[ 3 ] is 5
newarray[ 4 ] is 2
newarray[ 5 ] is 3
newarray[ 6 ] is 4
newarray[ 7 ] is 1
newarray[ 8 ] is 2
*/

---

This is what I was talking about with my last post. It doesn't matter if you have zero as a valid value in this array either.


Quzah.

I ended up getting sort of the same thing as kratz from quzah's comment:

Code:

---

  int oldArray[] = { 19, 16, 17, 18, 17, 15, 16, 18, 17, 19, 20, 16, 15, 18, 15 };
  int tempArray[sizeof oldArray / sizeof oldArray[0]];
 
  int maxOfNum = 2;
  int static countOfNum;
  int i, j;

  for (i = 0; i < 15; ++i) {
    countOfNum = 0;

    for (j = 0; j < 15; ++j) {
      if (tempArray[j] == oldArray[i])
        ++countOfNum;
    }

    if (countOfNum < maxOfNum) {
      tempArray[i] = oldArray[i];
      cout << tempArray[i] << ", ";
    }
  }

---

I believe it will accept 0 as a valid value too...

If you want it the new array to be the exact size of how many are carried over, why not just make this array a temp array, then copy over the contents of the temp array to a fresh array after.

Using my code you could do this a few ways:

1) Use a for loop to set all the values of the tempArray to some value, ie. 666. Then after all of the code, add another for loop that counts how many of the values in tempArray != 666, that will be the size of your newArray. Then simply make a for loop (to loop amount: size of the newArray) to take the values from the tempArray and put them into the newArray.

2) You could add another static int count and that counts inside (countOfNum < maxOfNum), which will end up being the amount of valid values in your tempArray. Then create newArray using that value as the size, then use a for loop to copy from tempArray to newArray.

I would like to thank everyone that contributed. You guys have been a huge help.