From a hash map, How to replace different values into each "key" that appeared in the input sentence?

I have a hashmap HashMap<String, ArrayList<String>> (e.g. Person-[p1,p2,p3]),
and an input string:

"Person talked to Person about Person"

How to replace different values into each "key" that appeared in the input sentence?
I want the result should be:

"p1 talked to p2 about p3"
"p1 talked to p3 about p2"
"p2 talked to p1 about p3"
"p2 talked to p3 about p1"
"p3 talked to p2 about p1"
"p3 talked to p1 about p2"

(combination all possible combinations of k elements in n). Is that any method or library support for this replacement?

--

I've done at the step of generating a simple replacing, but still stucked at generating the Permutations.

public static void main (String[] args) { 
HashMap<String, ArrayList<String>> data = new HashMap<>();
String test = "Person talked to Person about Person and Person";
//Just to populate.
ArrayList<String> input = new ArrayList<>();
input.add("p1");
input.add("p2");
input.add("p3");
data.put("Person", input);
if (StringUtils.countMatches(test, "Person") > data.get("Person").size()) {
System.out.println("Error: out of range");
}else {
for (int i=0 ; i<data.get("Person").size() ; i++) {
myReplace(test, "Person", data, i);
}
}
}
public static void myReplace(String input, String replaceValue, HashMap<String, ArrayList<String>> data, int indexOfValue) {
while (input.contains(replaceValue)) {
if (indexOfValue >= data.get(replaceValue).size()-1) {
indexOfValue = indexOfValue % data.get(replaceValue).size();
}
input = input.replaceFirst(replaceValue, data.get(replaceValue).get(indexOfValue));
indexOfValue++;
}
System.out.println(input);
}  

Here is a suggestion. This is partially pseudo code so it will not compile.

The key is not to use a map but to simply generate permutations of the people talking. For three people you have six permutations, four people, 24 permutations, n people, n! permutations. Here are the ones for three people:

p1, p2, p3
p1, p3, p2
p2, p1, p3
p2, p3, p1
p3, p1, p2
p3, p2, p1

So search the web (or this site) for a permutation algorithm (there are many out there) and do the following:

ArrayList<String> input = new ArrayList<>();
input.add("p1");
input.add("p2");
input.add("p3");
while(input = getNextPermutation(input)) {
String text = "Person talked to Person about Person";
for ( String p : input) {
text.replaceFirst("Person", p)
}
System.out.println(text);
}

The main challenge here will be integrating the permutation algorithm into the code. It does not have to be done as in the example.

More of a detailed comment on the accepted answer and your initial code - to truly move this around one-to-many, I would not use List but Set instead (guaranteeing that each subject is unique) if doing it this way.

On a different approach, I would just be working on the list itself or in my case array itself saving results once I know it's correct. And the array is not a 'plain' array in my case, it has an extra feature; arrays have the irritating property of ending but this one can rotate (I initially used it as a way to fade colours when generating histogram buckets that I wanted to 'fade'. Then I started using it frequently when generating test data for JUnits etc, a small array can generate any amount of test data for instance). In the simplest case you just use getNext() and when the pointer has passed the end index it just reverts to 0 again and that's pretty much it (I added some extra grab methods for different purposes).

A JUnit:

public class SpeakerTest {
private static final String[] PERSONS = new String[] { "p1", "p2", "p3" };
private static final ArrayRotator<String> ROTATOR = new ArrayRotator<>(PERSONS);
private static final String NL = System.getProperty("line.separator");
private static final String SUBJECT_ = "subject ";
private static final String TALKED_TO = " talked to ";
@Test
public void everyoneGetsToSpeakToTheOthers() {
StringBuilder message = new StringBuilder();
int subjectIndex = 0; // points to the subject speaking
int personsTalkedTo = 0; // how many each has talked to
while (subjectIndex < PERSONS.length) {
ROTATOR.getNext(); // the first person is always the subject self in our ordered array - skip it
while (personsTalkedTo < PERSONS.length) {
String adressedPerson = ROTATOR.getNext();
if (personsTalkedTo != PERSONS.length - 1) { // we know we always want to grab one less than the actual length
message.append(SUBJECT_).append(PERSONS[subjectIndex]).append(TALKED_TO).append(adressedPerson).append(NL);
}
personsTalkedTo++;
}
subjectIndex++; // move to the next subject
personsTalkedTo = 0; //..which so far talked to noone
// just print it and reset the builder
System.out.println(message.toString());
message.delete(0, message.length());
}
}
}

produces output

subject p1 talked to p2
subject p1 talked to p3
subject p2 talked to p3
subject p2 talked to p1
subject p3 talked to p1
subject p3 talked to p2

and it will work for any number of persons. If you want to save results in a map you can do this instead of printing.

The little Rotator tool that you feed with any array of anything which, again, is useful for many purposes:

public class ArrayRotator<T> {
private final T[] array;
private int index;
private static final Random RANDOM = new Random(731111245);
private enum Direction {
FORWARD, BACKWARD
}
public enum RenderMethod {
NEXT, RANDOM, PHASED_NEXT
}
private Direction direction;
public ArrayRotator(T[] array) {
if (array == null || array.length < 2) {
throw new IllegalArgumentException("You need top ship an array of no less than 2 elements!");
}
this.array = array;
index = -1;
direction = Direction.FORWARD;
}
public T getNext() {
index++;
if (index > array.length - 1) {
index = 0;
}
return array[index];
}
public T getRandom() {
return array[RANDOM.nextInt((array.length - 1) + 1)];
}
public T getNextPhading() {
if (direction == Direction.FORWARD) {
index++;
} else {
index--;
if (index < 0) {
direction = Direction.FORWARD;
index++;
}
}
if (index > array.length - 1) {
direction = Direction.BACKWARD;
index--;
}
return array[index];
}
public T[] get(RenderMethod method, int numberOfItems) {
List<T> list = new ArrayList<>();
switch (method) {
case NEXT:
for (int i = 0; i < numberOfItems; i++) {
list.add(getNext());
}
return (T[]) list.toArray();
case RANDOM:
for (int i = 0; i < numberOfItems; i++) {
list.add(getRandom());
}
return (T[]) list.toArray();
case PHASED_NEXT:
for (int i = 0; i < numberOfItems; i++) {
list.add(getNextPhading());
}
return (T[]) list.toArray();
default: throw new RuntimeException(String.format("Not supported mode %s", method.name()));
}
}
}

It is also possible to use Java Streams in this scenario and generate the needed result. Here is the working solution -

public void test(){
String p1 = "P1";
String p2 = "P2";
String p3 = "P3";
List<String> personList = List.of(p1, p2, p3);
List<String> resultList = new ArrayList<>();
personList
.stream()
.forEach(px -> personList // 1st Loop over all Person List
.stream()
.filter(not(px::equals)) // Filter to exclude the px person
.forEach(py -> personList // 2nd loop over filtered Person List
.stream()
.filter(p -> !(p.equals(px) || p.equals(py))) // Filter to exclude both px and py
.forEach(pz ->  // 3rd loop over filtered Person List
resultList.add(String.format("%s talked to %s about %s", px, py, pz))) // Prepare the result
)
);
for(String result: resultList) {
System.out.println(result);
}
}

Generated Output

P1 talked to P2 about P3
P1 talked to P3 about P2
P2 talked to P1 about P3
P2 talked to P3 about P1
P3 talked to P1 about P2
P3 talked to P2 about P1

You can do it using replaceFirst. And assuring you only have three inputs

    HashMap<String, ArrayList<String>> data = new HashMap<>();
//Just to populate.
ArrayList<String> input = new ArrayList<>();
input.add("p1");
input.add("p2");
input.add("p3");
data.put("Person", input);
data.put("Person2", input);
data.put("Person3", input);
String test = "Person talked to Person about Person";
//End of populate
data.forEach((k, v) -> {
String newS = test.replaceFirst("Person", v.get(0));
newS = newS.replaceFirst("Person", v.get(1));
newS = newS.replaceFirst("Person", v.get(0));
System.out.println(newS);
});