Thread: Array with at most n duplicates

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    6

    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

  2. #2
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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?

  3. #3
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    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...
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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

  5. #5
    Registered User
    Join Date
    Jul 2005
    Posts
    6
    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

  6. #6
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    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.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  7. #7
    Registered User
    Join Date
    Jul 2005
    Posts
    6
    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.........

  8. #8
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    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

  9. #9
    Banned
    Join Date
    Jun 2005
    Posts
    594
    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.

  10. #10
    Registered User
    Join Date
    Jul 2005
    Posts
    6
    I am not allowed to sort the first array

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  12. #12
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    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:

    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:

    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.
    Last edited by Dae; 07-14-2005 at 12:00 AM.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  14. #14
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    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.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-25-2008, 01:50 AM
  2. 1-D array
    By jack999 in forum C++ Programming
    Replies: 24
    Last Post: 05-12-2006, 07:01 PM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM