How can I generate a random sample of unique vertex pairings from a undirected graph, with uniform probability?

I’m working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random entity pair, remove it from the pool, then randomly select the next entity pair.

That would be like creating a random sample of vertex pairs from a complete graph.

However, this time around the undirected graph is now

  • incomplete
  • with a possibility that the graph might be disconnected.

I thought about using the above method but realized that my sample would not have a uniform probability of being chosen, as probabilities of pairings are no longer independent of each other due to uneven vertex degrees.

I’m banging my head at the wall for this. It’s best for research that I generate a sample with uniform probability. Given that my graph has around n = 5000 vertices, is there an algorithm that i could use such that the resulting sample fulfils these conditions?

  1. There are no duplicates in the sample (all vertices in the graph only is paired once).
  2. The remaining vertices that are not in the sample do not have an edge with each other. (They are unpaired and cannot be paired)
  3. The sample generated that meets the above two criteria should have a uniform probability of being chosen as compared to any other sample that fulfils the above two points.

There appear to be some work done for bipartite graphs as seen on this stackoverflow discussion here. The algorithms described obtains a near-uniform sample but doesn’t seem to be able to apply to this case.

Independent C library or function (on Linux) to programmatically generate a self-signed certificate [closed]

Is there a simple C library or function to programmatically generate a self-signed certificate in C on Ubuntu? Of course, one can execute a simple system("....") call to execute a CLI. I am looking for a native, small, stand-alone library just for this purpose with possibly added functionality but not with the full-weight of TLS implementations such as openssl, boringssl, mbedTls, etc.

Generate all combinations for variables and insert into temp table

0

I have one requirement there are 4 variables and i want all combinations of 4 variables and insert into temp table .

DECLARE StartDateTime DATETIME; DECLARE Age INT;  DECLARE Duration INT ; DECLARE TotalDD INT;  CREATE TEMPORARY TABLE tempTable(     Duration INT,     TotalDD INT,     Age INT,     StartDateTime DATETIME,     ); SET Age = 16; SET TotalDD = 14; SET Duration = 30; SET StartDateTime = CURDATE(); 

Excepted Result:

Duration age TotalDD StartDateTime 30 null null null null 16 null null 30 null null null 30 16 null null null null 14 20200622 30 null 14 null 30 16 null 20200622 

……….. ………. so on

How do I help newbies generate characters without being in person?

Background: I am about to start running a virtual D&D5e game over Zoom (I don’t have a choice of platform) through the local library. I have invited four of my friends to join, and only one has ever played before (he plays a lvl 5 paladin in my other group and wants to do a paladin or fighter this time). None of them have the 5e books or even know the basics of generating characters.

Usually, when I help new people for their first character, we meet in person and talk, bounce things off each other, banter, interrupt each other, and only then do we even work on the mechanics. However, COVID-19 has made it so we cannot safely do that anymore.

I have access to Roll20, but nobody else does and we cannot use it in game. The library is pretty strict on that. Most communication is done by text, with a little email as well. I effectively have a week to generate 4 characters for 4 mostly-new players before the first session, plus now one for the librarian. We are starting at lvl 7 (that is where the other group is and most will be using the same characters).

How do we generate ideas and then match those with mechanics without being in person?

Update: I emailed the librarian earlier to see if the other players would be willing to make new characters or regress their characters to a lower level, probably lvl 3. I will edit when I get a response. I figure I can point her to all the “start them at lower level” responses here and that should help my case.

Algorithm to generate combinations of n elements from n sets of m elements

Suppose I have 3 sets of 2 elements: [A, B], [C, D], [E, F], and I wanted to generate all possible combinations of 1 element from each set, such that the result of the algorithm would be:

[A, C, E], [A, C, F], [A, D, E], [A, D, F], [B, C, E], [B, C, F], [B, D, E], [B, D, F] 

What algorithm can I use to generate all combinations. Keep in mind that I’m looking for an algorithm that will work on any number of sets that have any number of elements, the above is just an example. Also, remember that I’m looking for an algorithm to actually generate the combinations, not just count them.

How to generate a CSR (certificate signing request) for creating a limited CA (Certificate Authority) with LibreSSL?

Related to this (too broad) question: How to implement my PKI?

I have a self-signed CA (ca0)

I would like to create a CA (ca1) with limited power derived from that first CA. ca1 should only be able to sign certificates for *.foo.com and for foo.com.

From this question, I found out that the Name Constraints extension is probably what I want.

The key for ca1 is already created and is ca1.foo.key.pem.

I already have an incomplete command for creating the request:

libressl req -new -sha512 -key ca1.foo.key.pem -out ca1.foo.csr.pem 

What should I add to that line to limit ca1’s power to what I want?

Elements of Programming Interviews – 16.4 Generate Power Set – solution 1 time complexity question

hope you all are doing well.

I have a question about the time complexity of solution 1 for question 16.4 – Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien.

The question instructs the reader to “Write a function that takes as input a set and returns its power set”. The input is the set S = {0,1,2}.

enter image description here

I understand that there are at most 2^n recursive calls of the method directedSoFar. However, I don’t understand why we spend O(n) time within a call of directedSoFar. There are no loops inside the method, only 2 lines at the recursive case to add and remove elements into the current selectedSoFar solution, and another 2 lines at the base case. Doesn’t this mean that we only spend constant time within a call, and not O(n) time?

I’ve struggled with this for a while, and have posted on the official forum as well as Reddit, but got no responses. I would appreciate it if anyone would be generous enough to help me.

Thank you

Is it possible to generate an equality function based on the data to be compared? [closed]

Two Booleans are equal if the’re the same value, two numbers similarly. Two sets are equal if they have the same elements. In case of checking two sets for equality we can use the following scheme/racket function:

(define (same-set? l1 l2)   (and (subset? l1 l2) (subset? l2 l1))) 

How would such a function be generated automatically?

The basic properties of an equivalence relation are:

Substitution property: For any quantities a and b and any expression F(x), if a = b, then F(a) = F(b) (if both sides make sense, i.e. are well-formed). Some specific examples of this are:

For any real numbers a, b, and c, if a = b, then a + c = b + c (here F(x) is x + c);

For any real numbers a, b, and c, if a = b, then a − c = b − c (here F(x) is x − c);

For any real numbers a, b, and c, if a = b, then ac = bc (here F(x) is xc);

For any real numbers a, b, and c, if a = b and c is not zero, then a/c = b/c (here F(x) is x/c).

Reflexive property: For any quantity a, a = a. Symmetric property: For any quantities a and b, if a = b, then b = a. Transitive property: For any quantities a, b, and c, if a = b and b = c, then a = c.

Is it possible to generate a function that obeys the above properties? Would that be enough? Could knowing the type of data help?

If you have any ideas on how to improve this question or tag it please comment.

PostgreSQL – Generate multiple running totals w/ group by day (Generate Series)

I’m having trouble figuring out a way to make this query work.

I have a set of transactions of stock purchases by users and I want to keep track of a running balance of each stock as the year progresses. I am using a windowing function to track the running balance but for some reason I cannot get the GROUP BY portion of this query to work.

It continues to have duplicate days in the result set even when I attempt to group by the date (created_at). Sample below:

select   t.customer_id,   t.created_at::date,   sum(case when t.stock_ticker = 'tsla' then t.amount end) over (order by t.created_at::date rows unbounded preceding) as tsla_running_amount,   sum(case when t.stock_ticker = 'goog' then t.amount end) over (order by t.created_at::date rows unbounded preceding) as goog_running_amount, from transactions t group by t.created_at, t.customer_id, t.stock_ticker, t.amount order by t.created_at desc; 

The results here always comes back with multiple records per day, when I want them to be grouped all into one day.

After doing some research I attempted cast the “created_at” to ::date inside of the group by fuction as well, but I get a:

“Column t.created_at must appear in the GROUP BY clause or be used in an aggregate function” error every single time.”

In addition, the results are only going to show the day’s in which a transaction has happened for a user. I need to be able to show a ROW for each day in a time series (1 year) even if the user did not make a transaction on that day. (Using the most recent running balance on the row instead)

I think that using “generate_series” is the proper way to do this, but I am having trouble understanding how to fit it in.

Thank you in advance!