Hi,
I'm looking for an efficient way to create the oposite of a
list of numbers.
For example, suppose I have this list of numbers:
100
200
300
I want to generate a list of all numbers between 1 and 999 that
exclude the numbers in this list.
Any suggestions are welcome.
Regards,
Eduardo
Jul 23 '05
19 2127
Mark P wrote: Eduardo Bezerra wrote:
Actually I oversimplified my question, so let me refine it. The list is not a list of integers, in reallity it's a list of strings numbers with a maximun lenght of 15 characters.
For example:
"526" "5261" "526212" "52621"
So what are you trying to find? All strings of length <= 15 that aren't in your list? That would be an enormous amount of data so I assume it's something else. But what?
My guess is, he is on to 'set operations'.
Given two sets of items: A and B, find the difference A - B
--
Karl Heinz Buchegger kb******@gascad .at
Mark P <no*@my.real.em ail> wrote in message news:<_E******* **********@news svr13.news.prod igy.com>... Eduardo Bezerra wrote:
Actually I oversimplified my question, so let me refine it. The list is not a list of integers, in reallity it's a list of strings numbers with a maximun lenght of 15 characters.
For example:
"526" "5261" "526212" "52621"
So what are you trying to find? All strings of length <= 15 that aren't in your list? That would be an enormous amount of data so I assume it's something else. But what?
Hello Mark,
I took some time to return to this thread because the requirements
of my problem changed and now it is settled.
I need to generate a list of the numbers that are not an exact match
and also do not start with any of the numbers in a list.
For example, given a list of string numbers such as:
"12"
"5625"
"56254"
"562542"
For the above given list, the resultant "barring" list of string
numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9
"10" "11" "13" "14" "15" "16" "17" "18" "19"
"50" "51" "52" "53" "54" "55" "57" "58" "59"
"560" "561" "563" "564" "565" "566" "567" "568" "569"
"5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
This generation much be very fast because it is for a real time
system.
Any comments, suggestions are much appreciated.
Best regards,
Eduardo
Eduardo Bezerra wrote: Mark P <no*@my.real.em ail> wrote in message news:<_E******* **********@news svr13.news.prod igy.com>... Eduardo Bezerra wrote:
Actually I oversimplified my question, so let me refine it. The list is not a list of integers, in reallity it's a list of strings numbers with a maximun lenght of 15 characters.
For example:
"526" "5261" "526212" "52621"
So what are you trying to find? All strings of length <= 15 that aren't in your list? That would be an enormous amount of data so I assume it's something else. But what?
Hello Mark,
I took some time to return to this thread because the requirements of my problem changed and now it is settled.
I need to generate a list of the numbers that are not an exact match and also do not start with any of the numbers in a list.
For example, given a list of string numbers such as:
"12" "5625" "56254" "562542"
For the above given list, the resultant "barring" list of string numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9 "10" "11" "13" "14" "15" "16" "17" "18" "19" "50" "51" "52" "53" "54" "55" "57" "58" "59" "560" "561" "563" "564" "565" "566" "567" "568" "569" "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
This generation much be very fast because it is for a real time system.
But it still is an enormous list!
Earlier you mentioned 15 characters. Is that still true?
So your above resultant list would also include:
"500"
"501" .. "599"
"5000"
"5001" .. "5999"
"50000"
"50001" .. "59999"
"500000"
....
"5000000"
....
That would be a pretty *huge* list!
--
Karl Heinz Buchegger kb******@gascad .at
Eduardo Bezerra wrote: Mark P <no*@my.real.em ail> wrote in message news:<_E******* **********@news svr13.news.prod igy.com>... Eduardo Bezerra wrote:
Actually I oversimplified my question, so let me refine it. The list is not a list of integers, in reallity it's a list of strings numbers with a maximun lenght of 15 characters.
For example:
"526" "5261" "526212" "52621" So what are you trying to find? All strings of length <= 15 that aren't in your list? That would be an enormous amount of data so I assume it's something else. But what?
Hello Mark,
I took some time to return to this thread because the requirements of my problem changed and now it is settled.
I need to generate a list of the numbers that are not an exact match and also do not start with any of the numbers in a list.
For example, given a list of string numbers such as:
"12" "5625" "56254" "562542"
For the above given list, the resultant "barring" list of string numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9 "10" "11" "13" "14" "15" "16" "17" "18" "19" "50" "51" "52" "53" "54" "55" "57" "58" "59" "560" "561" "563" "564" "565" "566" "567" "568" "569" "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
That 'list' is not complete, is it?
Eg. Why isn't "20" in the list. According to your description it should!
This generation much be very fast because it is for a real time system.
But it still is an enormous list!
Earlier you mentioned 15 characters. Is that still true?
So your above resultant list would also include:
"500"
"501" .. "599"
"5000"
"5001" .. "5999"
"50000"
"50001" .. "59999"
"500000"
....
"5000000"
....
That would be a pretty *huge* list!
--
Karl Heinz Buchegger kb******@gascad .at
"Eduardo Bezerra" <ed****@gmail.c om> wrote in message
news:58******** *************** ***@posting.goo gle.com... Mark P <no*@my.real.em ail> wrote in message news:<_E******* **********@news svr13.news.prod igy.com>... Eduardo Bezerra wrote:
....
I need to generate a list of the numbers that are not an exact match
What do you mean by "generate"?
and also do not start with any of the numbers in a list.
For example, given a list of string numbers such as:
"12" "5625" "56254" "562542"
For the above given list, the resultant "barring" list of string numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9 "10" "11" "13" "14" "15" "16" "17" "18" "19" "50" "51" "52" "53" "54" "55" "57" "58" "59" "560" "561" "563" "564" "565" "566" "567" "568" "569" "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
This generation much be very fast because it is for a real time system.
Leaving aside the issues raised in other responses. How will you use this
information? Are you going to be printing/displaying it? Are you going to be
traversing it from beginning to end? Are you just using it to test if a
value is a member?
Answering these questions would help lead to a specific solution. IMO, the
general approach, is to store the excluded values in a set. Treating them as
delimiters of intervals of values. I'd make the data type an integer(of
appropriate size for 15 decimal digits) and convert to std::string when
needed.
Jeff Flinn
Karl Heinz Buchegger <kb******@gasca d.at> wrote in message news:<42******* ********@gascad .at>... Eduardo Bezerra wrote: Mark P <no*@my.real.em ail> wrote in message news:<_E******* **********@news svr13.news.prod igy.com>... Eduardo Bezerra wrote:
> > Actually I oversimplified my question, so let me refine it. The list is not > a list of integers, in reallity it's a list of strings numbers with a maximun > lenght of 15 characters. > > For example: > > "526" > "5261" > "526212" > "52621"
So what are you trying to find? All strings of length <= 15 that aren't in your list? That would be an enormous amount of data so I assume it's something else. But what? Hello Mark,
I took some time to return to this thread because the requirements of my problem changed and now it is settled.
I need to generate a list of the numbers that are not an exact match and also do not start with any of the numbers in a list.
For example, given a list of string numbers such as:
"12" "5625" "56254" "562542"
For the above given list, the resultant "barring" list of string numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9 "10" "11" "13" "14" "15" "16" "17" "18" "19" "50" "51" "52" "53" "54" "55" "57" "58" "59" "560" "561" "563" "564" "565" "566" "567" "568" "569" "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
That 'list' is not complete, is it? Eg. Why isn't "20" in the list. According to your description it should!
This generation much be very fast because it is for a real time system.
But it still is an enormous list! Earlier you mentioned 15 characters. Is that still true? So your above resultant list would also include: "500" "501" .. "599" "5000" "5001" .. "5999" "50000" "50001" .. "59999" "500000" ... "5000000" ...
That would be a pretty *huge* list!
That 'list' is not complete, is it? Eg. Why isn't "20" in the list. According to your description it should!
Because there is no perfect match for "20" in the list and no number
in the list starts with (or contains) "20"
"Jeff Flinn" <NO****@nowhere .com> wrote in message news:<d4******* ***@bluegill.ad i.com>... "Eduardo Bezerra" <ed****@gmail.c om> wrote in message news:58******** *************** ***@posting.goo gle.com... Mark P <no*@my.real.em ail> wrote in message news:<_E******* **********@news svr13.news.prod igy.com>... Eduardo Bezerra wrote: ...
I need to generate a list of the numbers that are not an exact match
What do you mean by "generate"?
By "generate" I mean create or build the "barring" list. and also do not start with any of the numbers in a list.
For example, given a list of string numbers such as:
"12" "5625" "56254" "562542"
For the above given list, the resultant "barring" list of string numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9 "10" "11" "13" "14" "15" "16" "17" "18" "19" "50" "51" "52" "53" "54" "55" "57" "58" "59" "560" "561" "563" "564" "565" "566" "567" "568" "569" "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
This generation much be very fast because it is for a real time system. Leaving aside the issues raised in other responses. How will you use this information? Are you going to be printing/displaying it? Are you going to be traversing it from beginning to end? Are you just using it to test if a value is a member?
I'll be storing the result in a container, problably a set. It's not just
a test to see if a number is valid in the list, the goal is to build
the "barring" list. Answering these questions would help lead to a specific solution. IMO, the general approach, is to store the excluded values in a set. Treating them as delimiters of intervals of values. I'd make the data type an integer(of appropriate size for 15 decimal digits) and convert to std::string when needed.
Jeff Flinn
Karl Heinz Buchegger <kb******@gasca d.at> wrote in message news:<42******* ********@gascad .at>... Eduardo Bezerra wrote: Mark P <no*@my.real.em ail> wrote in message news:<_E******* **********@news svr13.news.prod igy.com>... Eduardo Bezerra wrote:
> > Actually I oversimplified my question, so let me refine it. The list is not > a list of integers, in reallity it's a list of strings numbers with a maximun > lenght of 15 characters. > > For example: > > "526" > "5261" > "526212" > "52621"
So what are you trying to find? All strings of length <= 15 that aren't in your list? That would be an enormous amount of data so I assume it's something else. But what?
Hello Mark,
I took some time to return to this thread because the requirements of my problem changed and now it is settled.
I need to generate a list of the numbers that are not an exact match and also do not start with any of the numbers in a list.
For example, given a list of string numbers such as:
"12" "5625" "56254" "562542"
For the above given list, the resultant "barring" list of string numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9 "10" "11" "13" "14" "15" "16" "17" "18" "19" "50" "51" "52" "53" "54" "55" "57" "58" "59" "560" "561" "563" "564" "565" "566" "567" "568" "569" "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
That 'list' is not complete, is it? Eg. Why isn't "20" in the list. According to your description it should!
This generation much be very fast because it is for a real time system.
But it still is an enormous list! Earlier you mentioned 15 characters. Is that still true? So your above resultant list would also include: "500" "501" .. "599" "5000" "5001" .. "5999" "50000" "50001" .. "59999" "500000" ... "5000000" ...
That would be a pretty *huge* list!
Continuing the explanation, "20" is not in the "barring" list because
any number starting with "2" is already excluded:
"0" "1" "2" "3" "4" "6" "7" "8" "9
^^^
"Eduardo Bezerra" <ed****@gmail.c om> wrote in message
news:58******** *************** *@posting.googl e.com... "Jeff Flinn" <NO****@nowhere .com> wrote in message news:<d4******* ***@bluegill.ad i.com>... "Eduardo Bezerra" <ed****@gmail.c om> wrote in message news:58******** *************** ***@posting.goo gle.com... > Mark P <no*@my.real.em ail> wrote in message > news:<_E******* **********@news svr13.news.prod igy.com>... >> Eduardo Bezerra wrote:
...
> I need to generate a list of the numbers that are not an exact match
What do you mean by "generate"?
By "generate" I mean create or build the "barring" list.
> and also do not start with any of the numbers in a list. > > For example, given a list of string numbers such as: > > "12" > "5625" > "56254" > "562542" > > For the above given list, the resultant "barring" list of string > numbers would be: > > "0" "1" "2" "3" "4" "6" "7" "8" "9 > "10" "11" "13" "14" "15" "16" "17" "18" "19" > "50" "51" "52" "53" "54" "55" "57" "58" "59" > "560" "561" "563" "564" "565" "566" "567" "568" "569" > "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629" > > This generation much be very fast because it is for a real time > system.
Leaving aside the issues raised in other responses. How will you use this information? Are you going to be printing/displaying it? Are you going to be traversing it from beginning to end? Are you just using it to test if a value is a member?
I'll be storing the result in a container, problably a set. It's not just a test to see if a number is valid in the list, the goal is to build the "barring" list.
And how do you plan on using this barring list? My point is that you may not
need to fully construct this list, which is probably antithetical to
real-time constraints. If the final use is to check if something is or is
not valid, you only need a function that provides that facility. If you do
need to present a user with values, probably only need to display a sub
range of values, perhaps implemented as an input iterator. Jeff Flinn
> For example, given a list of string numbers such as: "12" "5625" "56254" "562542"
For the above given list, the resultant "barring" list of string numbers would be:
"0" "1" "2" "3" "4" "6" "7" "8" "9 "10" "11" "13" "14" "15" "16" "17" "18" "19" "50" "51" "52" "53" "54" "55" "57" "58" "59" "560" "561" "563" "564" "565" "566" "567" "568" "569" "5620" "5621" "5622" "5623" "5624" "5626" "5627" "5628" "5629"
As I understand your problem, and assuming you have an "epsilon" value
representing a void string in the list, you need to find all the strings s
where the substring s(0,length(s)-2) is a prefix in the list and s not a
prefix in the list.
I think you could proceed that way:
1. Build a prefix tree P. (linear in the number of chars in your strings -
"epsilon" should be your root)
Each node N of P is tagged with the char it represents.
2. for each node N in P (width-first traversal)
2.1 for each char C in '0'..'9'
2.1.1 if N has a child tagged C then continue;
2.1.2 add the string made of all node from root to N + C to your list
The generation of the strings is linear in the size of the output which
might actually be exponential. I think you cannot do faster as you are bound
to the size of the output.
For instance, with the list 12, 5625, 56254, 562542 you would have the tree:
Node("", [
Node("1",[Node("2",[])]),
Node("5",[Node("6",[Node("2",[Node("5",[Node("4",[Node("2",[])])])])])])
])
You would start with node Node("",[...]), and add "0", "2", "3", ... (not
"1" and "5" since they are children of "")
Then you go with Node("1",[...]), and add "10", "11", "13", ... (not "2"
since it is a child of "1").
Then you go with Node("5",[...]), etc...
Then with Node("6") (and prefix "56")
If you don't want to have the values "120", "121", ... and so on you need
also to check if the current node is a leaf or not.
I hope it helps.
--
JS This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: massimo |
last post by:
Hey,
I wrote this program which should take the numbers entered and sort them
out. It doesn¹t matter what order, if decreasing or increasing.
I guess I'm confused in the sorting part. Anyone has any advices??
#include <iostream>
using namespace std;
|
by: simpleman |
last post by:
Hi,
I have an assignment that requires me to subtract two very large
unsigned integers
using linked list.AFAIK I have to manipulate data as character. But I
dont know how to get input into the linked list since the input will
all be in one line. eg.
1234567890. Also I have to use one integer per node.
Any help/suggestion will be greatly appreciated.
Thanks in advance
|
by: tron.thomas |
last post by:
The following code:
numbers =
for value in numbers:
value *= 2
print numbers
results in the following output:
|
by: Alex Fraser |
last post by:
Can negating a non-negative signed integer value ever overflow? Put another
way, can it be true that (mathematically) INT_MIN > -INT_MAX, LONG_MIN
> -LONG_MAX etc?
I know that typically it can't overflow, but if that isn't guaranteed, how
can I portably detect if it would?
Alex
|
by: Kasrav |
last post by:
hey guys it me again i got stuck in the middle of this program. The program starts with a list declaration of these numbers , i have to make sure the program outputs the following
1 The number of times 2 occurs in the list numbers
2 The position of the first occurrence of 2 in numbers.
3 The position of the next occurrence of 2 in numbers
4 The position of the last item in numbers
5 Sort the items of numbers.
6 The reversal of items in...
| |
by: shapper |
last post by:
Hello,
I have the following:
<ol id ="ol">
<li id="li1">item1</li>
<li id="li2">item2</li>
<ol>
Is it possible to display the List Items on the horizontal, i.e., side
|
by: badcrusher10 |
last post by:
Hello.
I'm having trouble figuring out what to do and how to do.. could someone explain to me what I need to do in order to work?
THIS IS WHAT I NEED TO DO:
Professor Snoop wants a program that will randomly generate 10 unique random numbers. Your job is to write a program that produces random permutations of the numbers 1 to 10. “Permutation” is a mathematical name for an arrangement. For example, there are six permutations of the...
|
by: vekka |
last post by:
Hi!
Programming language: C
I wondered if any of you are able to see what is wrong with my code. What I want to do is to find the union of a set of numbers. I use a singly linked list. and my union function is based on a simple merge algorithm.
There are four different sets: even numbers, odd numbers, prime numbers and non prime numbers.
When I run my program now, it prints out:
Even or Odd numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 .. 50 ...
|
by: antar2 |
last post by:
Hello,
I am a beginner in python.
following program prints the second element in list of lists 4 for the
first elements in list 4 that are common with the elements in list 5
list4 = ,,]
list5 =
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
| |
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |